SIAM Journal on Computing, Volume 14

Volume 14, Number 1, February 1985

• Paul M. B. Vitányi:
  An Optimal Simulation of Counter Machines. 1-33
  
• Paul M. B. Vitányi:
  An Optimal Simulation of Counter Machines: The ACM Case. 34-40
  
• Ker-I Ko, Uwe Schöning:
  On Circuit-Size Complexity and the Low Hierarchy in NP. 41-51
  
• Paris C. Kanellakis, Christos H. Papadimitriou:
  The Complexity of Distributed Concurrency Control. 52-74
  
• John H. Reif, Paul G. Spirakis:
  Unbounded Speed Variability in Distributed Communications Systems. 75-92
  
• Hiroshi Imai, Masao Iri, Kazuo Murota:
  Voronoi Diagram in the Laguerre Geometry and its Applications. 93-105
  
• Charles M. Fiduccia:
  An Efficient Formula for Linear Recurrences. 106-112
  
• Stuart A. Kurtz:
  Sparse Sets in NP - P: Relativizations. 113-119
  
• Andrew Chi-Chih Yao, F. Frances Yao:
  On Fault-Tolerant Networks for Sorting. 120-128
  
• Andrew Chi-Chih Yao:
  On the Expected Performance of Path Compression Algorithms. 129-133
  
• James E. Boyce, David P. Dobkin, Robert L. (Scot) Drysdale III, Leonidas J. Guibas:
  Finding Extremal Polygons. 134-147
  
• José L. Balcázar:
  Simplicity, Relativizations and Nondeterminism. 148-157
  
• Moon-Jung Chung, Fillia Makedon, Ivan Hal Sudborough, Jonathan S. Turner:
  Polynomial Time Algorithms for the Min Cut Problem on Degree Restricted Trees. 158-177
  
• Jean-Jacques Risler:
  Additive Complexity and Zeros of Real Polynomials. 178-183
  
• Susan Landau:
  Factoring Polynomials Over Algebraic Number Fields. 184-195
  , Erratum: SIAM J. Comput. 20(5): 998(1991)
• J. C. Lagarias:
  The Computational Complexity of Simultaneous Diophantine Approximation Problems. 196-209
  
• Norishige Chiba, Takao Nishizeki:
  Arboricity and Subgraph Listing Algorithms. 210-223
  
• Wen-Lian Hsu:
  Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs. 224-231
  
• Dan E. Willard:
  New Data Structures for Orthogonal Range Queries. 232-253
  
• Robert Endre Tarjan, Mihalis Yannakakis:
  Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. 254-255
  

Volume 14, Number 2, May 1985

• Edward M. McCreight:
  Priority Search Trees. 257-276
  
• Andrew Chi-Chih Yao:
  On the Complexity of Maintaining Partial Sums. 277-288
  
• Kazuhiko Matsumoto, Takao Nishizeki, Nobuji Saito:
  An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks. 289-302
  
• Uzi Vishkin, Avi Wigderson:
  Trade-Offs Between Depth and Width in Parallel Computation. 303-314
  
• John E. Hopcroft, Deborah Joseph, Sue Whitesides:
  On the Movement of Robot Arms in 2-Dimensional Bounded Regions. 315-333
  
• Minoru Ito, Motoaki Iwasaki, Tadao Kasami:
  Some Results on the Representative Instance in Relational Databases. 334-354
  
• Gopalakrishnan Vijayan, Avi Wigderson:
  Rectilinear Graphs and their Embeddings. 355-372
  
• György E. Révész:
  Axioms for the Theory of Lambda-Conversion. 373-382
  
• Werner Hartmann:
  On the Multiplicative Complexity of Modules Over Associative Algebras. 383-395
  
• Rüdiger Reischuk:
  Probabilistic Parallel Algorithms for Sorting and Selection. 396-409
  
• William F. Ogden, Rockford J. Ross, Karl Winklmann:
  An ``Interchange Lemma'' for Context-Free Languages. 410-415
  
• Edward G. Coffman Jr., T. T. Kadota, Larry A. Shepp:
  A Stochastic Model of Fragmentation in Dynamic Storage Allocation. 416-425
  
• Oscar H. Ibarra, Sam M. Kim, Shlomo Moran:
  Sequential Machine Characterizations of Trellis and Cellular Automata and Applications. 426-447
  
• Micha Sharir:
  Intersection and Closest-Pair Problems for a Set of Planar Discs. 448-468
  
• Erich Kaltofen:
  Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization. 469-489
  
• Jeffrey Scott Vitter, Wen-Chin Chen:
  Optimum Algorithms for a Model of Direct Chaining. 490-499
  
• M. R. Garey, David S. Johnson:
  Composing Functions to Minimize Image Size. 500-503
  

Volume 14, Number 3, August 1985

• James A. Reeds, N. J. A. Sloane:
  Shift-Register Synthesis (Modulo m). 505-513
  
• David G. Kirkpatrick, Maria M. Klawe:
  Alphabetic Minimax Trees. 514-526
  
• Susanne E. Hambrusch, Janos Simon:
  Solving Undirected Graph Problems on VLSI. 527-544
  
• Samuel W. Bent, Daniel Dominic Sleator, Robert Endre Tarjan:
  Biased Search Trees. 545-568
  
• Mohamed G. Gouda, Louis E. Rosier:
  Priority Networks of Communicating Finite State Machines. 569-584
  
• Timothy J. Long:
  On Restricting the Size of Oracles Compared with Restricting Access to Oracles. 585-597
  
• Richard Edwin Stearns, Harry B. Hunt III:
  On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata. 598-611
  
• Refael Hassin, Donald B. Johnson:
  An O(n log² n) Algorithm for Maximum Flow in Undirected Planar Networks. 612-624
  
• Eugene W. Myers:
  An O(E log E + I) Expected Time Algorithm for the Planar Segment Intersection Problem. 625-637
  
• Danny Dolev, Manfred K. Warmuth:
  Scheduling Flat Graphs. 638-657
  
• Jeremy Spinrad:
  On Comparability and Permutation Graphs. 658-670
  
• Ashok K. Chandra, Moshe Y. Vardi:
  The Implication Problem for Functional and Inclusion Dependencies is Undecidable. 671-677
  
• K. Kalorkoti:
  A Lower Bound for the Formula Size of Rational Functions. 678-687
  
• Marc Snir:
  On Parallel Searching. 688-708
  
• Marinus Veldhorst:
  Approximation of the Consecutive Ones Matrix Augmentation Problem. 709-729
  
• Zvi M. Kedem:
  Optimal Allocation of Area for Single-Chip Computations. 730-743
  
• Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh:
  Scheduling File Transfers. 744-780
  

Volume 14, Number 4, November 1985

• Greg N. Frederickson:
  Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications. 781-798
  
• J. Mark Keil:
  Decomposing a Polygon into Simpler Components. 799-817
  
• Appajosyula Satyanarayana, R. Kevin Wood:
  A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks. 818-832
  
• Stephen A. Cook, H. James Hoover:
  A Depth-Universal Circuit. 833-839
  
• Helmut Alt, Kurt Mehlhorn:
  Searching Semisorted Tables. 840-848
  
• Larry J. Stockmeyer:
  On Approximation Algorithms for #P. 849-861
  
• Robert Endre Tarjan, Uzi Vishkin:
  An Efficient Parallel Biconnectivity Algorithm. 862-874
  
• Jeffrey M. Jaffe:
  Distributed Multi-Destination Routing: The Constraints of Local Information. 875-888
  
• Henk Alblas:
  Finding Minimal Pass Sequences for Attribute Grammars. 889-914
  
• Ehab S. Elmallah, Charles J. Colbourn:
  Optimum Communication Spanning Trees in Series-Parallel Networks. 915-925
  
• Derek G. Corneil, Yehoshua Perl, Lorna K. Stewart:
  A Linear Recognition Algorithm for Cographs. 926-934
  
• Rohit Parikh, Ashok K. Chandra, Joseph Y. Halpern, Albert R. Meyer:
  Equations Between Regular Terms and an Application to Process Logic. 935-942
  
• Paul Walton Purdom Jr., Cynthia A. Brown:
  The Pure Literal Rule and Polynomial Average Time. 943-953
  
• Ulrich Faigle, Gerhard Gierz, Rainer Schrader:
  Algorithmic approaches to setup minimization. 954-965
  
• Michael F. Singer, B. David Saunders, B. F. Caviness:
  An Extension of Liouville's Theorem on Integration in Finite Terms. 966-990
  
• Sergiu Hart, Micha Sharir:
  Concurrent Probabilistic Programs, Or: How to Schedule if You Must. 991-1012
  
• Dan E. Willard:
  Searching Unindexed and Nonuniformly Generated Files in log log N Time. 1013-1029
  
• Debasis Mitra:
  Probabilistic Models and Asymptotic Results for Concurrent Processing with Exclusive and Non-Exclusive Locks. 1030-1051
  
• Deepak Kapur, Paliath Narendran:
  The Knuth-Bendix Completion Procedure and Thue Systems. 1052-1072
  

Last update Tue Feb 14 04:22:17 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page