Volume 19, Number 1, February 1990
- Michael A. Palis, Sunil M. Shende, David S. L. Wei:
An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages.
1-31
- Irvin Roy Hentzel, David Pokrass Jacobs:
Complexity and Unsolvability Properties of Nilpotency.
32-43
- Harry B. Hunt III, Richard Edwin Stearns:
The Complexity of Very Simple Boolean Formulas with Applications.
44-70
- Cheng Ng, Daniel S. Hirschberg:
Lower Bounds for the Stable Marriage Problem and its Variants.
71-77
- Hirofumi Yokouchi, Teruo Hikita:
A Rewriting System for Categorical Combinators with Multiple Arguments.
78-97
- George Labahn, Dong-Koo Choi, Stanley Cabay:
The Inverses of Block Hankel and Block Toeplitz Matrices.
98-123
- Joel Friedman:
A Density Theorem for Purely Iterative Zero Finding Methods.
124-132
- Michael L. Dowling:
A Fast Parallel Horner Algorithm.
133-142
- Dan Gusfield:
Very Simple Methods for All Pairs Network Flow Analysis.
143-155
- Edward R. Scheinerman:
On the Expected Capacity of Binomial and Random Concentrators.
156-163
- Greg N. Frederickson, Ravi Janardan:
Space-Efficient Message Routing in c-Decomposable Networks.
164-181
- H. James Hoover:
Feasible Real Functions and Arithmetic Circuits.
182-204
- Greg N. Frederickson, Donald B. Johnson:
Erratum: Generalized Selection and Ranking: Sorted Matrices.
205-206 ,
->SIAM J. Comput. 13(1): 14-30(1984)
Volume 19, Number 2, April 1990
- Miroslaw Kutylowski, Maciej Liskiewicz, Krzysztof Lorys:
Reversal Complexity Classes for Alternating Turing Machines.
207-221
- Jennifer Whitehead:
The Complexity of File Transfer Scheduling with Forwarding.
222-245
- Gianfranco Bilardi, Franco P. Preparata:
Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size.
246-255
- David Peleg, Eli Upfal:
A Time-Randomness Trade-Off for Oblivious Routing.
256-266
- David A. Plaisted:
A Heuristic Algorithm for Small Separators in Arbitrary Graphs.
267-280
- Laura A. Sanchis, Mark A. Fulk:
On the Efficient Generation of Language Instances.
281-296
- Pankaj K. Agarwal, Micha Sharir:
Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection.
297-321
- Christos H. Papadimitriou, Mihalis Yannakakis:
Towards an Architecture-Independent Analysis of Parallel Algorithms.
322-328
- Robert W. Floyd, Donald E. Knuth:
Addition Machines.
329-340
- Jan J. M. M. Rutten:
Semantic Correctness for a Parallel Object-Oriented Language.
341-383
- Christopher B. Wilson:
On the Decomposability of NC and AC.
384-396
- Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao:
Parallel Depth-First Search in General Directed Graphs.
397-409
Volume 19, Number 3, June 1990
Volume 19, Number 4, August 1990
- David M. Mount:
The Number of Shortest Paths on the Surface of a Polyhedron.
593-611
- Francis Y. L. Chin, H. F. Ting:
Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees.
612-626
- J. M. Jover, Thomas Kailath, Hanoch Lev-Ari, S. K. Rao:
On the Analysis of Synchronous Computing Systems.
627-643
- Mariangiola Dezani-Ciancaglini, Betti Venneri:
Partial Types and Intervals.
644-568
- Bill Jackson:
Shortest Circuit Covers and Postman Tours in Graphs with a Nowhere Zero 4-Flow.
659-665
- Alan M. Frieze, Colin McDiarmid, Bruce A. Reed:
Greedy Matching on the Line.
666-672
- Robert Y. Levin, Alan T. Sherman:
A Note on Bennett's Time-Space Tradeoff for Reversible Computation.
673-677
- Torben Hagerup:
Planar Depth-First Search in O(log n) Parallel Time.
678-704
- Wansoo T. Rhee:
A Note on Optimal Bin Packing and Optimal Bin Covering with Items of Random Size.
705-710
- Douglas R. Stinson:
Some Observations on Parallel Algorithms for Fast Exponentiation in GF(2^n).
711-717
- Faith E. Fich, Avi Wigderson:
Toward Understanding Exclusive Read.
718-727
- Ashfaq A. Munshi, Barbara Simons:
Scheduling Sequential Loops on Parallel Processors.
728-741
- Mark W. Krentel:
On Finding and Verifying Locally Optimal Solutions.
742-749
- Thomas Dubé:
The Structure of Polynomial Ideals and Gröbner Bases.
750-773
Volume 19, Number 5, October 1990
- Jeanette P. Schmidt, Alan Siegel:
The Spatial Complexity of Oblivious k-Probe Hash Functions.
775-786
- Erich Grädel:
Domino Games and Complexity.
787-804
- Robert Cypher, Jorge L. C. Sanz, L. Snyder:
The Hough Transform has O(N) Complexity on N x N Mesh Connected Computers.
805-820
- Luc Devroye, Louise Laforest:
An Analysis of Random d-Dimensional Quad Trees.
821-832
- Klaus W. Wagner:
Bounded Query Classes.
833-846
- Keqin Li, Kam-Hoi Cheng:
On Three-Dimensional Packing.
847-867
- Joan M. Lucas:
Postorder Disjoint Set Union is Linear.
868-882
- Kazuo Iwano, Kenneth Steiglitz:
A Semiring on Convex Polygons and Zero-Sum Cycle Problems.
883-901
- Kurt Mehlhorn, Stefan Näher, Monika Rauch:
On the Complexity of a Game Related to the Dictionary Problem.
902-906
- Daniel Bienstock:
Linear-Time Test for Small Face Covers in Any Fixed Surface.
907-911
- John H. Reif, Stephen R. Tate:
Optimal Size Integer Division Circuits.
912-924
- John K. Johnstone, Chandrajit L. Bajaj:
Sorting Points Along an Algebraic Curve.
925-967
- Alberto Apostolico, Mikhail J. Atallah, Lawrence L. Larmore, Scott McFaddin:
Efficient Parallel Algorithms for String Editing and Related Problems.
968-988
Volume 19, Number 6, December 1990
- Zvi Galil, Kunsoo Park:
An Improved Algorithm for Approximate String Matching.
989-999
- George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran:
Linear Programming with Two Variables per Inequality in Poly-Log Time.
1000-1010
- Cynthia Dwork, Larry J. Stockmeyer:
A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata.
1011-1023
- Kazuo Sugihara, Ichiro Suzuki, Masafumi Yamashita:
The Searchlight Scheduling Problem.
1024-1040
- D. T. Lee, Majid Sarrafzadeh, Ying-Fung Wu:
Minimum Cuts for Circular-Arc Graphs.
1041-1050
- Dany Breslauer, Zvi Galil:
An Optimal O(log log n) Time Parallel String Matching Algorithm.
1051-1058
- Dima Grigoriev, Marek Karpinski, Michael F. Singer:
Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields.
1059-1063
- Noga Alon, Mauricio Karchmer, Avi Wigderson:
Linear Circuits over GF(2).
1064-1067
- Joel Friedman:
Random Polynomials and Approximate Zeros of Newton's Method.
1068-1099
- Jack H. Lutz:
Category and Measure in Complexity Classes.
1100-1131
- Kazuo Murota:
Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation.
1132-1161
Copyright © Sat Nov 28 22:33:33 2009
by Michael Ley (ley@uni-trier.de)
