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-742
Volume 14,
Number 4,
November 1985
- Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh:
Scheduling File Transfers.
743-780
- 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 Atttibute 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
Copyright © Tue Nov 10 01:01:50 2009
by Michael Ley (ley@uni-trier.de)
