SIAM Journal on Computing, Volume 21

Volume 21, Number 1, February 1992

• Dan Halperin, Mark H. Overmars, Micha Sharir:
  Efficient Motion Planning for an L-Shaped Object. 1-23
  
• Ricardo A. Baeza-Yates, Rafael Casas, Josep Díaz, Conrado Martinez:
  On the Average Size of the Intersection of Binary Trees. 24-32
  
• Jehoshua Bruck, Roman Smolensky:
  Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms. 33-42
  
• Mihály Geréb-Graus, Danny Krizanc:
  The Average Complexity of Parallel Comparison Merging. 43-47
  
• Luc Devroye, Wojciech Szpankowski, Bonita Rais:
  A Note on the Height of Suffix Trees. 48-53
  
• Michael Ben-Or, Richard Cleve:
  Computing Algebraic Formulas Using a Constant Number of Registers. 54-58
  
• Li-Hui Tsai:
  Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling. 59-64
  
• Bruce Hendrickson:
  Conditions for Unique Graph Realizations. 65-84
  
• Susan Landau:
  Simplification of Nested Radicals. 85-110
  
• David W. Krumme, George Cybenko, K. N. Venkataraman:
  Gossiping in Minimal Time. 111-139
  
• Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos:
  Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems. 140-150
  
• Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg:
  Efficient Embeddings of Trees in Hypercubes. 151-162
  
• Timothy Law Snyder:
  On the Exact Location of Steiner Points in General Dimension. 163-180
  
• Paul Fischer, Hans-Ulrich Simon:
  On Learning Ring-Sum-Expansions. 181-192
  
• Nathan Linial:
  Locality in Distributed Graph Algorithms. 193-201
  

Volume 21, Number 2, April 1992

• Thang Nguyen Bui, Andrew Peck:
  Partitioning Planar Graphs. 203-215
  
• Wen-Guey Tzeng:
  A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata. 216-227
  
• Alfred Menezes, Paul C. van Oorschot, Scott A. Vanstone:
  Subgroup Refinement Algorithms for Root Finding in GF(q). 228-239
  
• David P. Helmbold, Robert H. Sloan, Manfred K. Warmuth:
  Learning Integer Lattices. 240-266
  
• Franco P. Preparata, Roberto Tamassia:
  Efficient Point Location in a Convex Spatial Cell-Complex. 267-280
  
• Qingzhou Wang, Kam-Hoi Cheng:
  A Heuristic of Scheduling Parallel Tasks and its Analysis. 281-294
  
• Pang C. Chen:
  Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs. 295-315
  
• Seinosuke Toda, Mitsunori Ogiwara:
  Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy. 316-328
  
• Yossi Azar:
  Lower Bounds for Threshold and Symmetric Functions in Parallel Computation. 329-338
  
• Chandrajit L. Bajaj, Tamal K. Dey:
  Convex Decomposition of Polyhedra and Robustness. 339-364
  
• David W. Krumme:
  Fast Gossiping for the Hypercube. 365-380
  
• Beverly Jamison, Stephan Olariu:
  Recognizing P_4 Sparse Graphs in Linear Time. 381-406
  

Volume 21, Number 3, June 1992

• Zvi Galil, Raffaele Giancarlo:
  On the Exact Complexity of String Matching: Upper Bounds. 407-437
  
• B. K. Natarajan:
  Probably Approximate Learning Over Classes of Distributions. 438-449
  
• Christos H. Papadimitriou:
  The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem. 450-465
  
• John H. Reif, Sandeep Sen:
  Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems. 466-485, (Erratum: SIAM J. Comput. 23(2): 447-448 (1994))
  
• Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani:
  Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph. 486-506
  
• R. W. Gatterdam:
  Algorithms for Splicing Systems. 507-520
  
• Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe:
  Relating Equivalence and Reducibility to Sparse Sets. 521-539
  
• Pankaj K. Agarwal:
  Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number. 540-570
  
• Jarkko Kari:
  The Nilpotency Problem of One-Dimensional Cellular Automata. 571-586
  
• Qian-Ping Gu, Akira Maruoka:
  Learning Monotone Boolean Functions by Uniformly Distributed Examples. 587-599
  

Volume 21, Number 4, August 1992

• Elefterios A. Melissaratos, Diane L. Souvaine:
  Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions. 601-638
  
• Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe:
  Dynamic Tree Embeddings in Butterflies and Hypercubes. 639-654
  
• H. Venkateswaran:
  Circuit Definitions of Nondeterministic Complexity Classes. 655-670
  
• Bernard Chazelle:
  An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra. 671-696
  
• Ming Li, Luc Longpré, Paul M. B. Vitányi:
  The Power of the Queue. 697-712
  
• David Aldous, Micha Hofri, Wojciech Szpankowski:
  Maximum Size of a Dynamic Data Structure: Hashing with Lazy Deletion Revisited. 713-732
  
• K. Ganesan, Steven Homer:
  Complete Problems and Strong Polynomial Reducibilities. 733-742
  
• Richard Chang:
  On the Structure of Bounded Queries to Arbitrary NP Sets. 743-754
  
• Samuel R. Buss, S. Cook, A. Gupta, V. Ramachandran:
  An Optimal Parallel Algorithm for Formula Evaluation. 755-780
  
• Dario Bini, Luca Gemignani:
  On the Complexity of Polynomial Zeros. 781-799
  

Volume 21, Number 5, October 1992

• Richard Koch:
  Increasing the Size of a Network by a Constant Factor can Increase Performance by more than a Constant Factor. 801-823
  
• Lin Yu, Daniel J. Rosenkrantz:
  Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications. 824-855
  
• Dany Breslauer, Zvi Galil:
  A Lower Bound for Parallel String Matching. 856-862
  
• Ichiro Suzuki, Masafumi Yamashita:
  Searching for a Mobile Intruder in a Polygonal Region. 863-888
  
• Danny Dolev, Tomás Feder:
  Determinism vs. Nondeterminism in Multiparty Communication Complexity. 889-895
  
• John H. Reif, Stephen R. Tate:
  On Threshold Circuits and Polynomial Computation. 896-908
  
• Bettina Just:
  Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions. 909-926
  
• Lenwood S. Heath, Arnold L. Rosenberg:
  Laying out Graphs Using Queues. 927-958
  
• Michael C. Loui, David R. Luginbuhl:
  Optimal On-Line Simulations of Tree Machines by Random Access Machines. 959-971
  
• Siu-Wing Cheng, Ravi Janardan:
  New Results on Dynamic Planar Point Location. 972-999
  
• Egon Balas, Jue Xue:
  Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs. 1000, (see: SIAM J. Comput. 20(2): 209-221 (1991))
  

Volume 21, Number 6, December 1992

• Ding-Zhu Du, Frank K. Hwang:
  Reducing the Steiner Problem in a Normed Space. 1001-1007
  
• James Renegar:
  On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae. 1008-1025
  
• Wei-Kuan Shih, T. C. Chern, Wen-Lian Hsu:
  An O(n² log n) Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs. 1026-1046
  
• Zvi Galil, Giuseppe F. Italiano:
  Fully Dynamic Algorithms for 2-Edge Connectivity. 1047-1069
  
• Charles U. Martel, Arvin Park, Ramesh Subramonian:
  Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers. 1070-1099
  
• Jie Wang:
  Polynomial Time Productivity, Approximations, and Levelability. 1100-1111
  
• Wolfgang W. Bein, Jerzy Kamburowski, Matthias F. M. Stallmann:
  Optimal Reductions of Two-Terminal Directed Acyclic Graphs. 1112-1129
  
• Greg N. Frederickson, D. J. Guan:
  Preemptive Ensemble Motion Planning on a Tree. 1130-1152
  
• Martin Tompa:
  Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs. 1153-1160
  
• Stephen Bellantoni, Toniann Pitassi, Alasdair Urquhart:
  Approximation and Small-Depth Frege Proofs. 1161-1179
  
• Helmut Prodinger:
  External Internal Nodes in Digital Search Trees via Mellin Transforms. 1180-1183
  
• Brandon Dixon, Monika Rauch, Robert Endre Tarjan:
  Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time. 1184-1192
  
• Mohammad Amin Shokrollahi:
  Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves. 1193-1198
  

Last update Thu May 23 19:26:38 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page