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