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 updated on Fri May 24 06:30:52 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page