SIAM Journal on Computing, Volume 22

Volume 22, Number 1, February 1993

• Amos Fiat, Moni Naor:
  Implicit O(1) Probe Search. 1-10
  
• 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
  
• Noam Nisan, Avi Wigderson:
  Rounds in Communication Complexity Revisited. 211-219
  

Volume 22, Number 2, April 1993

• Omer Berkman, Uzi Vishkin:
  Recursive Star-Tree Parallel Data Structure. 221-242
  
• Jorma Tarhio, Esko Ukkonen:
  Approximate Boyer-Moore String Matching. 243-260
  
• 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
  
• Miklos Santha, Christopher B. Wilson:
  Limiting Negations in Constant Depth Circuits. 294-302
  
• 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
  
• Shlomo Moran, Manfred K. Warmuth:
  Gap Theorems for Distributed Computation. 379-394
  
• Ronald V. Book, Jack H. Lutz:
  On Languages With Very High Space-Bounded Kolmogorov Complexity. 395-402
  
• Noga Alon, Moni Naor:
  Coin-Flipping Games Immune Against Linear-Sized Coalitions. 403-417
  
• 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
  
• Daniel Bienstock, Nicole Diaz:
  Blocking Small Cuts in a Network, and Related Problems. 482-499
  
• 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
  
• Jonathan F. Buss, Judy Goldsmith:
  Nondeterminism Within P. 560-572
  
• 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
  
• Dario Bini, Victor Y. Pan:
  Improved Parallel Polynomial Division. 617-626
  
• 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
  
• A. Dür, Johannes Grabmeier:
  Applying Coding Theory to Sparse Interpolation. 695-704
  
• 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
  
• Pankaj K. Agarwal, Marco Pellegrini, Micha Sharir:
  Counting Circular Arc Intersections. 778-793
  
• Pankaj K. Agarwal, Jirí Matousek:
  Ray Shooting and Parametric Search. 794-806
  
• Michael J. Kearns, Ming Li:
  Learning in the Presence of Malicious Errors. 807-837
  
• Joseph Naor, Moni Naor:
  Small-Bias Probability Spaces: Efficient Constructions and Applications. 838-856
  
• David Harel, Danny Raz:
  Deciding Properties of Nonregular Programs. 857-874
  
• Reuven Bar-Yehuda, Amos Israeli, Alon Itai:
  Multiple Communication in Multihop Radio Networks. 875-887
  

Volume 22, Number 5, October 1993

• Tsan-sheng Hsu, Vijaya Ramachandran:
  Finding a Smallest Augmentation to Biconnect a Graph. 889-912
  
• Bernd Halstenberg, Rüdiger Reischuk:
  Different Modes of Communication. 913-934
  
• Udi Manber, Eugene W. Myers:
  Suffix Arrays: A New Method for On-Line String Searches. 935-948
  
• Andreas Blass, Yuri Gurevich:
  Randomizing Reductions of Search Problems. 949-975
  
• Ruey-Der Lou, Majid Sarrafzadeh:
  An Optimal Algorithm for the Maximum Three-Chain Problem. 976-993
  
• Joan Feigenbaum, Lance Fortnow:
  Random-Self-Reducibility of Complete Sets. 994-1005
  
• 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
  
• Béla Bollobás, István Simon:
  Probabilistic Analysis of Disjoint Set Union Algorithms. 1053-1074
  
• 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

• Tao Jiang, Bala Ravikumar:
  Minimal NFA Problems are Hard. 1117-1141
  
• Jiazhen Cai, Xiaofeng Han, Robert Endre Tarjan:
  An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem. 1142-1162
  
• Oded Goldreich, Hugo Krawczyk, Michael Luby:
  On the Existence of Pseudorandom Generators. 1163-1175
  
• 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
  
• Wansoo T. Rhee, Michel Talagrand:
  On-Line Bin Packing of Items of Random Sizes, II. 1251-1256
  
• Ricard Gavaldà, Osamu Watanabe:
  On the Computational Complexity of Small Descriptions. 1257-1275
  
• 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
  
• Jiang-Hsing Chu, Gary D. Knott:
  A New Method for Computing Page-Fault Rates. 1319-1330
  
• Eyal Kushilevitz, Yishay Mansour:
  Learning Decision Trees Using the Fourier Spectrum. 1331-1348
  
• Richard Cole:
  Correction: Parallel Merge Sort. 1349, (see: SIAM J. Comput. 17(4): 770-785 (1988))
  

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