SIAM Journal on Computing, Volume 11

Volume 11, Number 1, February 1982

• Oscar H. Ibarra, Brian S. Leininger:
  Straight-Line Programs with One Input Variable. 1-14
  
• Oscar H. Ibarra, Brian S. Leininger:
  The Complexity of the Equivalence Problem for Simple Loop-Free Programs. 15-27
  
• J. H. Halton, Routo Terada:
  A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One. 28-46
  
• Arnon Rosenthal:
  Dynamic Programming is Optimal for Nonserial Optimization Problems. 47-59
  
• Edward G. Coffman Jr., Micha Hofri:
  On the Expected Performance of Scanning Disks. 60-70
  
• Robert P. Burton, David R. Smith:
  A Hidden-Line Algorithm for Hyperspace. 71-80
  
• John H. Reif, Robert Endre Tarjan:
  Symbolic Program Analysis in Almost-Linear Time. 81-93
  
• Don Coppersmith, Douglas Stott Parker Jr., C. K. Wong:
  Analysis of a General Mass Storage System. 94-116
  
• Harold N. Gabow, Oded Kariv:
  Algorithms for Edge Coloring Bipartite Graphs and Multigraphs. 117-129
  
• Martin Tompa:
  Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations. 130-137
  
• Lawrence T. Kou:
  Minimum Variance Huffman Codes. 138-148
  
• Dan E. Willard:
  Polygon Retrieval. 149-165
  
• Emily P. Friedman, Sheila A. Greibach:
  A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors. 166-183
  
• Per M. Jensen, Bernhard Korte:
  Complexity of Matroid Property Algorithms. 184-190
  
• Kellogg S. Booth, J. Howard Johnson:
  Dominating Sets in Chordal Graphs. 191-199
  

Volume 11, Number 2, May 1982

• Michael R. Levy, T. S. E. Maibaum:
  Continuous Data Types. 201-216
  
• Douglas Comer, Michael J. O'Donnell:
  Geometric Problems with Application to Hashing. 217-226
  
• Jia-Wei Hong, Arnold L. Rosenberg:
  Graphs that are Almost Binary Trees. 227-242
  
• James R. Bitner:
  An Asymptotically Optimal Algorithm for the Dutch National Flag Problem. 243-262
  
• Francesco Romani:
  Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication. 263-267
  
• John Keohane, John C. Cherniavsky, Peter B. Henderson:
  On Transforming Control Structures. 268-286
  
• Allan Borodin, Stephen A. Cook:
  A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. 287-297
  
• Jacobo Valdes, Robert Endre Tarjan, Eugene L. Lawler:
  The Recognition of Series Parallel Digraphs. 298-313
  
• Joseph JáJá, Janos Simon:
  Parallel Algorithms in Graph Theory: Planarity Testing. 314-328
  
• David Lichtenstein:
  Planar Formulae and Their Uses. 329-343
  
• Shlomo Moran:
  On the Accepting Density Hierarchy in NP. 344-349
  
• Leslie G. Valiant:
  A Scheme for Fast Parallel Communication. 350-361
  
• T. C. Hu, M. T. Shing:
  Computation of Matrix Chain Products. Part I. 362-373
  
• Daniel J. Lehmann:
  On Primality Tests. 374-375
  
• Robert Sedgewick, Thomas G. Szymanski, Andrew Chi-Chih Yao:
  The Complexity of Finding Cycles in Periodic Functions. 376-390
  
• Mihalis Yannakakis:
  Freedom from Deadlock of Safe Locking Policies. 391-408
  

Volume 11, Number 3, August 1982

• Nathan Linial, Michael Tarsi:
  The Counterfeit Coin Problem Revisited. 409-415
  
• Michael J. Fischer, Albert R. Meyer, Mike Paterson:
  Omega(n log n) Lower Bounds on Length of Boolean Formulas. 416-427
  
• Andrew Chi-Chih Yao, F. Frances Yao:
  On the Average-Case Complexity of Selecting the kth Best. 428-447
  
• Eitan M. Gurari:
  The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable. 448-452
  
• Micha Hofri, Percy Tzelnic:
  The Working Set Size Distribution for the Markov Chain Model of Program Behavior. 453-466
  
• Don Coppersmith:
  Rapid Multiplication of Rectangular Matrices. 467-471
  
• Don Coppersmith, Shmuel Winograd:
  On the Asymptotic Complexity of Matrix Multiplication. 472-492
  
• Barry K. Rosen:
  A Lubricant for Data Flow Analysis. 493-511
  
• Katsuto Nakajima, S. Louis Hakimi, Jan Karel Lenstra:
  Complexity Results for Scheduling Tasks in Fixed Intervals on Two Types of Machines. 512-520
  
• Bernhard Banaschewski, Evelyn Nelson:
  Completions of Partially Ordered Sets. 521-528
  
• Dominique Gouyou-Beauchamps:
  The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs. 529-539
  
• Richard Cole, John E. Hopcroft:
  On Edge Coloring Bipartite Graphs. 540-546
  
• Henry W. Davis, Leon E. Winslow:
  Computational Power in Query Languages. 547-554
  
• Dorit S. Hochbaum:
  Approximation Algorithms for the Set Covering and Vertex Cover Problems. 555-556
  
• Aaron M. Tenenbaum, Richard M. Nemes:
  Two Spectra of Self-Organizing Sequential Search Algorithms. 557-566
  
• Mikhail J. Atallah:
  Finding the Cyclic Index of an Irreducible, Nonnegative Matrix. 567-570
  
• Ronald V. Book, Christopher B. Wilson, Xu Mei-Rui:
  Relativizing Time, Space, and Time-Space. 571-581
  
• Udai Gupta, D. T. Lee, C. K. Wong:
  Ranking and Unranking of 2-3 Trees. 582-590
  
• Jia-Wei Hong:
  On Some Deterministic Space Complexity Problems. 591-601
  
• Virgil D. Gligor, David Maier:
  Finding Augmented-Set Bases. 602-609
  

Volume 11, Number 4, November 1982

• Kohei Noshita:
  Predicting the Number of Distinct Elements in a Multiset. 611-619
  
• Richard M. Karp, Christos H. Papadimitriou:
  On Linear Characterizations of Combinatorial Optimization Problems. 620-632
  
• Teofilo F. Gonzalez, Joseph JáJá:
  Evaluation of Arithmetic Expressions with Algebraic Identities. 633-662
  
• Norishige Chiba, Takao Nishizeki, Nobuji Saito:
  An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs. 663-675
  
• Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter:
  Hamilton Paths in Grid Graphs. 676-686
  
• Tsu-Wu J. Chou, George E. Collins:
  Algorithms for the Solution of Systems of Linear Diophantine Equations. 687-708
  
• James O. Achugbue, Francis Y. L. Chin:
  Scheduling the Open Shop to Minimize Mean Flow Time. 709-720
  
• Andrew Chi-Chih Yao:
  On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems. 721-736
  
• Richard P. Brent, Leslie M. Goldschlager:
  Some Area-Time Tradeoffs for VLSI. 737-747
  
• Kurt Mehlhorn:
  A Partial Analysis of Height-Balanced Trees Under Random Insertions and Deletions. 748-760
  
• Michael B. Smyth, Gordon D. Plotkin:
  The Category-Theoretic Solution of Recursive Domain Equations. 761-783
  
• Christian Ronse:
  Optimization of Cost and Delay in Cellular Permutation Networks. 784-788
  
• A. O. L. Atkin, Richard G. Larson:
  On a Primality Test of Solovay and Strassen. 789-791
  

Last update Fri May 24 20:47:27 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page