SIAM Journal on Computing, Volume 22
Volume 22, Number 1, February 1993
- Zvi Galil, Giuseppe F. Italiano: Maintaining the 3-Edge-Connected Components of a Graph On-Line. 11-28
- Héctor J. Hernández, Ke Wang: On the Boundedness of Constant-Time-Maintainable Database Schemes. 29-45
- Weizhen Mao: Tight Worst-Case Performance Bounds for Next-k-Fit Bin Packing. 46-56
- Greg N. Frederickson: A Note on the Complexity of a Simple Transportation Problem. 57-61
- Robert Cypher: A Lower Bound on the Size of Shellsort Sorting Networks. 62-71
- Joel Friedman: A Note on Poset Geometries. 72-78
- Sukhamay Kundu: An O(n) Algorithm for Determining the Subregion-Tree Representation of a Rectangular Dissection. 79-101
- Viliam Geffert: Tally Versions of the Savitch and Immerman-Szelepcsenyi Theorems for Sublogarithmic Space. 102-113
- Michio Oyamaguchi: NV-Sequentiality: A Decidable Condition for Call-by-Need Computations in Term-Rewriting Systems. 114-135
- Kazuo Iwama: ASPACE(o(log log n)) is Regular. 136-146
- Peter Bro Miltersen: The Complexity of Malign Measures. 147-156
- Joseph Cheriyan, Ming-Yang Kao, Ramakrishna Thurimella: Scan-First Search and Sparse Certificates: An Improved Parallel Algorithms for k-Vertex Connectivity. 157-174
- Andreas Weber: Decomposing Finite-Valued Transducers and Deciding Their Equivalence. 175-202
- Jan Kratochvíl, Petr Savický, Zsolt Tuza: One More Occurrence of Variables Makes Satisfiability Jump From Trivial to NP-Complete. 203-210
Volume 22, Number 2, April 1993
- Wenceslas Fernandez de la Vega, Sampath Kannan, Miklos Santha: Two Probabilistic Results on Merging. 261-271
- Wayne Goddard, Claire Kenyon, Valerie King, Leonard J. Schulman: Optimal Randomized Algorithms for Local Sorting and Set-Maxima. 272-283
- Narendra Karmarkar, Richard M. Karp, Richard J. Lipton, László Lovász, Michael Luby: A Monte-Carlo Algorithm for Estimating the Permanent. 284-293
- Khaled M. Bugrara, Paul Walton Purdom Jr.: Average Time Analysis of Clause Order Backtracking. 303-317
- Chandrajit L. Bajaj, John F. Canny, Thomas Garrity, Joe D. Warren: Factoring Rational Polynomials Over the Complex Numbers. 318-331
- Edward G. Coffman Jr., Leopold Flatto, Paul E. Wright: Optimal Stochastic Allocation of Machines Under Waiting-Time Constraints. 332-348
- Gábor Galambos, Gerhard J. Woeginger: An On-Line Scheduling Heuristic With Better Worst Case Ratio Than Graham's List Scheduling. 349-355
- Robert Cypher: Theoretical Aspects of VLSI Pin Limitations. 356-378
- Ronald V. Book, Jack H. Lutz: On Languages With Very High Space-Bounded Kolmogorov Complexity. 395-402
- Herbert Edelsbrunner, Raimund Seidel, Micha Sharir: On the Zone Theorem for Hyperplane Arrangements. 418-429
Volume 22, Number 3, June 1993
- Ming-Yang Kao: Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components. 431-459
- Ming-Yang Kao, Gregory E. Shannon: Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees. 460-481
- Kok-Hoo Yeap, Majid Sarrafzadeh: Floor-Planning by Graph Dualization: 2-Concave Rectilinear Modules. 500-526
- Herbert Edelsbrunner, Tiow Seng Tan: A Quadratic Time Algorithm for the Minimax Length Triangulation. 527-551
- K. Kalorkoti: Inverting Polynomials and Formal Power Series. 552-559
- Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis: Parallel Complexity of the Connected Subgraph Problem. 573-586
- Donald S. Fussell, Vijaya Ramachandran, Ramakrishna Thurimella: Finding Triconnected Components by Local Replacement. 587-616
- Daniel J. Rosenkrantz, Harry B. Hunt III: The Complexity of Processing Hierarchical Specifications. 627-649
- Edward G. Coffman Jr., Leopold Flatto, Paul E. Wright: A Stochastic Checkpoint Optimization Problem. 650-659
Volume 22, Number 4, August 1993
- Andreas Goerdt: Regular Resolution Versus Unrestricted Resolution. 661-683
- Harald Niederreiter, Claus-Peter Schnorr: Local Randomness in Polynomial Random Number and Random Function Generators. 684-694
- Sally A. Goldman, Michael J. Kearns, Robert E. Schapire: Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions. 705-726
- Louise E. Moser, P. M. Melliar-Smith, Vivek Agrawala: Asynchronous Fault-Tolerant Total Ordering Algorithms. 727-750
- Arthur S. Goldstein, Edward M. Reingold: A Fibonacci Version of Kraft's Inequality Applied to Discrete Unimodal Search. 751-777
- Joseph Naor, Moni Naor: Small-Bias Probability Spaces: Efficient Constructions and Applications. 838-856
- Reuven Bar-Yehuda, Amos Israeli, Alon Itai: Multiple Communication in Multihop Radio Networks. 875-887
Volume 22, Number 5, October 1993
- Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire: Learning Binary Relations and Total Orders. 1006-1034
- Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger: Drawing Graphs in the Plane with High Resolution. 1035-1052
- Jack H. Lutz: A Pseudorandom Oracle Characterization of BPP. 1075-1086
- Mark Jerrum, Alistair Sinclair: Polynomial-Time Approximation Algorithms for the Ising Model. 1087-1116
Volume 22, Number 6, December 1993
- Jiazhen Cai, Xiaofeng Han, Robert Endre Tarjan: An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem. 1142-1162
- Wojciech Szpankowski: A Generalized Suffix Tree and its (Un)expected Asymptotic Behaviors. 1176-1198
- David R. Karger, Daphne Koller, Steven J. Phillips: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths. 1199-1217
- Xin He: On Finding the Rectangular Duals of Planar Triangular Graphs. 1218-1226
- Victor Y. Pan, John H. Reif: Fast and Efficient Parallel Solution of Sparse Linear Systems. 1227-1250
- Marek Karpinski, Thorsten Werther: VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions. 1276-1285
- Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jack Snoeyink: Computing a Face in an Arrangement of Line Segments and Related Problems. 1286-1302
- Bo Chen: A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times. 1303-1318
- Richard Cole: Correction: Parallel Merge Sort. 1349
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T201401 by the dblp team