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, (see: 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

Last update Fri May 24 20:47:29 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page