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