Volume 16, Number 1, February 1987

• 
  Christos H. Papadimitriou, John N. Tsitsiklis: On Stochastic Scheduling with In-Tree Precedence Constraints. 1-6
• 
  Ravindran Kannan, Gary L. Miller, Larry Rudolph: Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers. 7-16
• 
  Oded Shmueli, Alon Itai: Complexity of Views: Tree and Cyclic Schemas. 17-37
• 
  Russ Miller, Quentin F. Stout: Data Movement Techniques for the Pyramid Computer. 38-60
• 
  Richard Cole, Micha Sharir, Chee-Keng Yap: On k-Hulls and Related Problems. 61-77
• 
  Franz Aurenhammer: Power Diagrams: Properties, Algorithms and Applications. 78-96
• 
  Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Time-Space Tradeoff for Element Distinctness. 97-99
• 
  Friedhelm Meyer auf der Heide, Avi Wigderson: The Complexity of Parallel Sorting. 100-107
• 
  Douglas W. Jones: A Note on Bottom-Up Skew Heaps. 108-110
• 
  Dan Gusfield: Three Fast Algorithms for Four Problems in Stable Marriage. 111-128
• 
  Harry B. Hunt III, Daniel J. Rosenkrantz, Peter A. Bloniarz: On the Computational Complexity of Algebra on Lattices. 129-148
• 
  Frank D. Murgolo: An Efficient Approximation Scheme for Variable-Sized Bin Packing. 149-161
• 
  Hyeong-Ah Choi, S. Louis Hakimi: Scheduling File Transfers for Trees and Odd Cycles. 162-168
• 
  Costas Courcoubetis, Martin I. Reiman, Burton Simon: Stability of a Queueing System with Concurrent Service and Locking. 169-178
• 
  Peter D. Mosses, Gordon D. Plotkin: On Proving Limiting Completeness. 179-194
• 
  Wolfgang Maass, Amir Schorr: Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape. 195-202
• 
  Françoise Fogelman-Soulié, Gérard Weisbuch: Random Iterations of Threshold Networks and Associative Memory. 203-220

Volume 16, Number 2, April 1987

• 
  Karel Culik II, Juhani Karhumäki: The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDT0L Languages) is Decidable. 221-230
• 
  Ephraim Korach, Shlomo Moran, Shmuel Zaks: The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors. 231-236
• 
  Dan Gusfield, Charles U. Martel, David Fernández-Baca: Fast Algorithms for Bipartite Network Flow. 237-251
• 
  Dario Bini, Milvio Capovani: Tensor Rank and Border Rank of Band Toeplitz Matrices. 252-258
• 
  Jin-yi Cai, Gabriele E. Meyer: Graph Minimal Uncolorability is D^P-Complete. 259-277
• 
  Thomas Lickteig: The Computational Complexity of Division in Quadratic Extension Fields. 278-311
• 
  Takao Asano: An Application of Duality to Edge-Deletion Problems. 312-331
• 
  Irène Guessarian, José Meseguer: On the Axiomatization of ``If-Then-Else''. 332-357
• 
  Joseph Douglas Horton: A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph. 358-366
• 
  Oscar H. Ibarra, Michael A. Palis: On Efficient Simulations of Systolic Arrays of Random-Access Machines. 367-377
• 
  Charles Knessl, B. J. Matkowsky, Z. Schuss, Charles Tier: Asymptotic Expansions for a Closed Multiple Access System. 378-398
• 
  Micha Hofri, Keith W. Ross: On the Optimal Control of Two Queues with Server Setup Times and its Analysis. 399-420

Volume 16, Number 3, June 1987

• 
  Roberto Tamassia: On Embedding a Graph in the Grid with the Minimum Number of Bends. 421-444
• 
  Sam Toueg, Kenneth J. Perry, T. K. Srikanth: Fast Distributed Agreement. 445-457
• 
  Yossi Azar, Uzi Vishkin: Tight Comparison Bounds on the Complexity of Parallel Sorting. 458-464
• 
  Alan H. Mekler, Evelyn Nelson: Equational Bases for If-Then-Else. 465-485
• 
  Yuri Gurevich, Saharon Shelah: Expected Computation Time for Hamiltonian Path Problem. 486-502
• 
  Vijay K. Vaishnavi: Weighted Leaf AVL-Trees. 503-537, (Erratum: SIAM J. Comput. 19(3): 591 (1990))
• 
  Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Reliable Concurrency Control. 538-553
• 
  Donald K. Friesen: Tighter Bounds for LPT Scheduling on Uniform Processors. 554-560
• 
  Micha Sharir: On Shortest Paths Amidst Convex Polyhedra. 561-572
• 
  T. C. Hu, Michelle L. Wachs: Binary Search on a Tape. 573-590
• 
  Arjen K. Lenstra: Factoring Multivariate Polynomials over Algebraic Number Fields. 591-598

Volume 16, Number 4, August 1987

• 
  Dan Gusfield: Optimal Mixed Graph Augmentation. 599-612
• 
  William I. Gasarch: Oracles for Deterministic versus Alternating Classes. 613-627
• 
  Daniel S. Hirschberg, Lawrence L. Larmore: The Least Weight Subsequence Problem. 628-638
• 
  Christos H. Papadimitriou, Jeffrey D. Ullman: A Communication-Time Tradeoff. 639-646
• 
  Joseph S. B. Mitchell, David M. Mount, Christos H. Papadimitriou: The Discrete Geodesic Problem. 647-668
• 
  Teofilo F. Gonzalez, Sing-Ling Lee: A 1.6 Approximation Algorithm for Routing Multiterminal Nets. 669-704
• 
  B. John Oommen, E. R. Hansen: List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations. 705-716
• 
  Nicholas C. Wormald: Generating Random Unlabelled Graphs. 717-727
• 
  Peter Widmayer, Ying-Fung Wu, C. K. Wong: On Some Distance Problems in Fixed Orientations. 728-746
• 
  David P. Helmbold, Ernst W. Mayr: Two Processor Scheduling is in NC. 747-759
• 
  Neil Immerman: Languages that Capture Complexity Classes. 760-778

Volume 16, Number 5, October 1987

• 
  Louis E. Rosier, Hsu-Chun Yen: Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning Omega-Machines. 779-807
• 
  Helmut Alt, Torben Hagerup, Kurt Mehlhorn, Franco P. Preparata: Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones. 808-835
• 
  Wenqui Huang, Xiangdong Yu: A DNF without Regular Shortest Consensus Path. 836-840
• 
  Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. 841-851
• 
  Stuart A. Kurtz: A Note on Randomized Polynomial Time. 852-853
• 
  Anna Lubiw: Doubly Lexical Orderings of Matrices. 854-879
• 
  Pierre McKenzie, Stephen A. Cook: The Parallel Complexity of Abelian Permutation Group Problems. 880-909
• 
  Harry B. Hunt III, Richard Edwin Stearns: Nonlinear Algebra and Optimization on Rings are ``Hard''. 910-929
• 
  Joachim von zur Gathen: Computing Powers in Parallel. 930-945
• 
  Bernd Becker, Günter Hotz: On the Optimal Layout of Planar Graphs with Fixed Boundary. 946-972

Volume 16, Number 6, December 1987

• 
  Robert Paige, Robert Endre Tarjan: Three Partition Refinement Algorithms. 973-989
• 
  Mark Chao Kuen Yang, Jun Siung Huang, Yuan-Chieh Chow: Optimal Parallel Sorting Scheme by Order Statistics. 990-1003
• 
  Greg N. Frederickson: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications. 1004-1022
• 
  Alistair Moffat, Tadao Takaoka: An All Pairs Shortest Path Algorithm with Expected Time O(n² log n). 1023-1031
• 
  Nicholas Pippenger: Sorting and Selecting in Rounds. 1032-1038
• 
  Karl R. Abrahamson: Generalized String Matching. 1039-1051
• 
  Alan M. Frieze: On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients. 1052-1072
• 
  Micha Hofri, Alan G. Konheim: Padded Lists Revisited. 1073-1114
• 
  Lawrence L. Larmore: Height Restricted Optimal Binary Trees. 1115-1123
• 
  Edward R. Scheinerman: Almost Sure Fault Tolerance in Random Graphs. 1124-1134
• 
  Oscar H. Ibarra, Tao Jiang: On One-Way Cellular Arrays. 1135-1154
• 
  John A. Morrison, Larry A. Shepp, Christopher J. Van Wyk: A Queueing Analysis of Hashing with Lazy Deletion. 1155-1164

last updated on Sat May 18 06:35:41 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page