SIAM Journal on Computing, Volume 16

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 update Fri May 17 20:45:21 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page