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
- Koheil 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
Copyright © Thu Nov 26 19:45:55 2009
by Michael Ley (ley@uni-trier.de)
