Volume 18, Number 1, February 1989
- Jeffery Westbrook, Robert Endre Tarjan:
Amortized Analysis of Algorithms for Set Union with Backtracking.
1-11 BibTeX
- Karl R. Abrahamson, Andrew Adler, Rachel Gelbart, Lisa Higham, David G. Kirkpatrick:
The Bit Complexity of Randomized Leader Election on a Ring.
12-29 BibTeX
- Giorgio Gallo, Michael D. Grigoriadis, Robert Endre Tarjan:
A Fast Parametric Maximum Flow Algorithm and Applications.
30-55 BibTeX
- Robert E. Wilber:
Lower Bounds for Accessing Binary Search Trees with Rotations.
56-67 BibTeX
- Norbert Korte, Rolf H. Möhring:
An Incremental Linear-Time Algorithm for Recognizing Interval Graphs.
68-81 BibTeX
- Lawrence L. Larmore:
Minimum Delay Codes.
82-94 BibTeX
- Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung:
The Boolean Hierarchy II: Applications.
95-111 BibTeX
- Greg N. Frederickson, Mandayam A. Srinivas:
Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems.
112-138 BibTeX
- Wansoo T. Rhee, Michel Talagrand:
Optimal Bin Packing with Items of Random Sizes II.
139-151 BibTeX
- Edward T. Ordman:
Minimal Threshold Separators and Memory Requirements for Synchronization.
152-165 BibTeX
- Edward G. Coffman Jr., J. C. Lagarias:
Algorithms for Packing Squares: A Probabilistic Analysis.
166-185 BibTeX
- Shafi Goldwasser, Silvio Micali, Charles Rackoff:
The Knowledge Complexity of Interactive Proof Systems.
186-208 BibTeX
Volume 18, Number 2, April 1989
- Thomas Lickteig:
A Lower Bound on the Complexity of Division in Finite Extension Fields and Inversion in Quadratic Alternative Algebras.
209-215 BibTeX
- Gianfranco Bilardi, Alexandru Nicolau:
Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines.
216-228 BibTeX
- David Peleg, Eli Upfal:
The Token Distribution Problem.
229-243 BibTeX
- Jing-Jang Hwang, Yuan-Chieh Chow, Frank D. Anger, Chung-Yee Lee:
Scheduling Precedence Graphs in Systems with Interprocessor Communication Times.
244-257 BibTeX
- Noga Alon, Yossi Azar:
Finding an Approximate Maximum.
258-267 BibTeX
- Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman:
Bounds on Universal Sequences.
268-277 BibTeX
- J. Michael Steele, Timothy Law Snyder:
Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization.
278-287 BibTeX
- Torben Hagerup, Marek Chrobak, Krzysztof Diks:
Optimal Parallel 5-Colouring of Planar Graphs.
288-300 BibTeX
- Riccardo Melen, Jonathan S. Turner:
Nonblocking Multirate Networks.
301-313 BibTeX
- Joseph Y.-T. Leung, Gilbert H. Young:
Minimizing Schedule Length Subject to Minimum Flow Time.
314-326 BibTeX
- Joseph Naor, Moni Naor, Alejandro A. Schäffer:
Fast Parallel Algorithms for Chordal Graphs.
327-349 BibTeX
- James Renegar:
On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials.
350-370 BibTeX
- F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, Mike Paterson:
Partitioning Space for Range Queries.
371-384 BibTeX
- Kazuo Iwama:
CNF Satisfiability Test by Counting and Polynomial Average Time.
385-391 BibTeX
- Ker-I Ko:
Relativized Polynomial Time Hierarchies Having Exactly K Levels.
392-408 BibTeX
- Khaled M. Bugrara, Youfang Pan, Paul Walton Purdom Jr.:
Exponential Average Time for the Pure Literal Rule.
409-418 BibTeX
- Mark K. Goldberg, Thomas H. Spencer:
A New Parallel Algorithm for the Maximal Independent Set Problem.
419-427 BibTeX
Volume 18, Number 3, June 1989
- Edward P. F. Chan:
A Design Theory for Solving the Anomalies Problem.
429-448 BibTeX
- Shouwen Tang, Osamu Watanabe:
On Tally Relativizations of BP-Complexity Classes.
449-462 BibTeX
- Shuo-Yen Robert Li:
Dynamic Programming by Exchangeability.
463-472 BibTeX
- Wansoo T. Rhee, Michel Talagrand:
Optimal Bin Packing with Items of Random Sizes III.
473-486 BibTeX
- Wansoo T. Rhee, Michel Talagrand:
Optimal Bin Covering with Items of Random Size.
487-498 BibTeX
- Mikhail J. Atallah, Richard Cole, Michael T. Goodrich:
Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms.
499-532 BibTeX
- H. Venkateswaran, Martin Tompa:
A New Pebble Game That Characterizes Parallel Complexity Classes.
533-549 BibTeX
- Merrick L. Furst, Ravi Kannan:
Succinct Certificates for Almost All Subset Sum Problems.
550-558 BibTeX
- Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa:
Two Applications of Inductive Counting for Complementation Problems.
559-578 BibTeX
,
Erratum:
SIAM J. Comput. 18(6): 1283(1989) BibTeX
- Francisco Barahona, Éva Tardos:
Note on Weintraub's Minimum-Cost Circulation Algorithm.
579-583 BibTeX
- Michael Clausen:
Fast Fourier Transforms for Metabelian Groups.
584-593 BibTeX
- Sanguthevar Rajasekaran, John H. Reif:
Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms.
594-607 BibTeX
- Graham H. Norton:
Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for GF(q)[x].
608-624 BibTeX
- Neil Immerman:
Expressibility and Parallel Complexity.
625-638 BibTeX
Volume 18, Number 4, August 1989
- George Labahn, Stanley Cabay:
Matrix Padé Fractions and Their Computation.
639-657 BibTeX
- Costas S. Iliopoulos:
Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix.
658-669 BibTeX
- Costas S. Iliopoulos:
Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Infinite Abelian Groups and Solving Systems of Linear Diophantine Equations.
670-678 BibTeX
- Andrew Chi-Chih Yao:
On the Complexity of Partial Order Productions.
679-689 BibTeX
- Barbara B. Simons, Manfred K. Warmuth:
A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs.
690-710 BibTeX
- Zvi Galil, Stuart Haber, Moti Yung:
Minimum-Knowledge Interactive Proofs for Decision Problems.
711-739 BibTeX
- David Peleg, Jeffrey D. Ullman:
An Optimal Synchronizer for the Hypercube.
740-747 BibTeX
- Pravin M. Vaidya:
Space-Time Trade-Offs for Orthogonal Range Queries.
748-758 BibTeX
- Nader H. Bshouty:
A Lower Bound for Matrix Multiplication.
759-765 BibTeX
- Charles H. Bennett:
Time/Space Trade-Offs for Reversible Computation.
766-776 BibTeX
- Philippe Jacquet, Wojciech Szpankowski:
Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation.
777-791 BibTeX
- Richard Cole, Jeffrey S. Salowe, William L. Steiger, Endre Szemerédi:
An Optimal-Time Algorithm for Slope Selection.
792-810 BibTeX
- Franco P. Preparata, Roberto Tamassia:
Fully Dynamic Point Location in a Monotone Subdivision.
811-830 BibTeX
- Karel Culik II, Jan K. Pachl, Sheng Yu:
On the Limit Sets of Cellular Automata.
831-842 BibTeX
- Greg N. Frederickson, Ravi Janardan:
Efficient Message Routing in Planar Networks.
843-857 BibTeX
Volume 18, Number 5, October 1989
- Johan Håstad, Bettina Just, J. C. Lagarias, Claus-Peter Schnorr:
Polynomial Time Algorithms for Finding Integer Relations among Real Numbers.
859-881 BibTeX
- Shoshana Anily, Refael Hassin:
Ranking the Best Binary Trees.
882-892 BibTeX
- Guy W. Cherry:
An Analysis of the Rational Exponential Integral.
893-905 BibTeX
- Rakesh M. Verma, Steven W. Reyner:
An Analysis of a Good Algorithm for the Subtree Problem, Corrected.
906-908 BibTeX
,
->SIAM J. Comput. 6(4): 730-732(1977) BibTeX
- Wansoo T. Rhee, Michel Talagrand:
The Complete Convergence of Best Fit Decreasing.
909-918 BibTeX
- Wansoo T. Rhee, Michel Talagrand:
The Complete Convergence of First Fit Decreasing.
919-938 BibTeX
- Ravindra K. Ahuja, James B. Orlin, Robert Endre Tarjan:
Improved Time Bounds for the Maximum Flow Problem.
939-954 BibTeX
- Wayne Eberly:
Very Fast Parallel Polynomial Arithmetic.
955-976 BibTeX
- Ernst-Erich Doberkat:
Topological Completeness in an Ideal Model for Polymorphic Types.
977-989 BibTeX
- Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer:
The Distributed Firing Squad Problem.
990-1012 BibTeX
- Harold N. Gabow, Robert Endre Tarjan:
Faster Scaling Algorithms for Network Problems.
1013-1036 BibTeX
- Cynthia A. Brown, Larry Finkelstein, Paul Walton Purdom Jr.:
A New Base Change Algorithm for Permutation Groups.
1037-1047 BibTeX
- Keith E. Humenik:
Ratio Estimators are Maximum-Likelihood Estimators for Non-Context-Free Grammars.
1048-1055 BibTeX
Volume 18, Number 6, December 1989
- Joseph Cheriyan, S. N. Maheshwari:
Analysis of Preflow Push Algorithms for Maximum Network Flow.
1057-1086 BibTeX
- Richard E. Ladner:
Polynomial Space Counting Problems.
1087-1097 BibTeX
- David Bernstein, Jeffrey M. Jaffe, Michael Rodeh:
Scheduling Arithmetic and Load Operations in Parallel with No Spilling.
1098-1127 BibTeX
- David Rappaport:
Computing Simple Circuits from a Set of Line Segments is NP-Complete.
1128-1139 BibTeX
- Umesh V. Vazirani, Vijay V. Vazirani:
The Two-Processor Scheduling Problem is in Random NC.
1140-1148 BibTeX
- Mark Jerrum, Alistair Sinclair:
Approximating the Permanent.
1149-1178 BibTeX
- Manfred Schimmler, Christoph Starke:
A Correction Network for N-Sorters.
1179-1187 BibTeX
- Zhiyuan Li, Edward M. Reingold:
Solution of a Divide-and-Conquer Maximin Recurrence.
1188-1200 BibTeX
- Pravin M. Vaidya:
Geometry Helps in Matching.
1201-1225 BibTeX
- Ming-Syan Chen, Kang G. Shin:
On Relaxed Squashed Embedding of Graphs into a Hypercube.
1226-1244 BibTeX
- Kaizhong Zhang, Dennis Shasha:
Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems.
1245-1262 BibTeX
- Bala Ravikumar, Oscar H. Ibarra:
Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation.
1263-1282 BibTeX
- Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa:
Erratum: Two Applications of Inductive Counting for Complementation Problems.
1283 BibTeX
,
->SIAM J. Comput. 18(3): 559-578(1989) BibTeX
Copyright © Tue May 27 18:34:10 2008
by Michael Ley (ley@uni-trier.de)
