SIAM Journal on Computing, Volume 19

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))

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

Burkhard Molzan:
Expressibility and Nonuniform Complexity Classes. 411-423
Helmut Seidl:
Deciding Equivalence of Finite Tree Automata. 424-437
Etienne Grandjean:
A Nontrivial Lower Bound for an NP Problem on Automata. 438-451
Nader H. Bshouty, Michael Kaminski:
Multiplication of Polynomials over Finite Fields. 452-456
Yinyu Ye:
A Class of Projective Transformations for Linear Programming. 457-466
Nader H. Bshouty:
Maximal Rank of m x n x (mn - k) Tensors. 467-471
Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer:
Flipping Persuasively in Constant Time. 472-499
David Eppstein:
Reset Sequences for Monotonic Automata. 500-510
Maciej Liskiewicz, Krzysztof Lorys:
Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones. 511-521
Richard Beigel:
Unbounded Searching Slgorithms. 522-537
Takis Sakkalis:
The Euclidean Algorithm and the Degree of the Gauss Map. 538-543
Fred S. Annexstein, Marc Baumslag, Arnold L. Rosenberg:
Group Action Graphs and Parallel Architectures. 544-569
Alan Wagner, Derek G. Corneil:
Embedding Trees in a Hypercube is NP-Complete. 570-590
Vijay K. Vaishnavi:
Erratum: Weighted Leaf AVL-Trees. 591, (see: SIAM J. Comput. 16(3): 503-537 (1987))

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

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

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