Volume 17, Number 1, February 1988

• 
  Yehoshua Sagiv: On Bounded Database Schemes and Bounded Horn-Clause Programs. 1-22
• 
  Donald K. Friesen, Frederick S. Kuhl: Analysis of a Hybrid Algorithm for Packing Unequal Bins. 23-40
• 
  Sumio Masuda, Kazuo Nakajima: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph. 41-52
• 
  Daniel Bienstock, Clyde L. Monma: On the Complexity of Covering Vertices by Faces in a Planar Graph. 53-76
• 
  Jyrki Katajainen, Jan van Leeuwen, Martti Penttonen: Fast Simulation of Turing Machines by Random Access Machines. 77-88
• 
  Masanori Fushimi: Designing a Uniform Random Number Generator Whose Subsequences are k-Distributed. 89-99
• 
  Ulrich Faigle, György Turán: Sorting and Recognition Problems for Ordered Sets. 100-113
• 
  David M. Nicol: Expected Performance of m-Solution Backtracking. 114-127
• 
  Richard Cole, Uzi Vishkin: Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time. 128-142, (Correction: SIAM J. Comput. 22(6): 1349 (1993))
• 
  Robert Endre Tarjan, Christopher J. Van Wyk: An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon. 143-178

Volume 17, Number 2, April 1988

• 
  Eric Bach: How to Generate Factored Random Numbers. 179-193
• 
  Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr: RSA and Rabin Functions: Certain Parts are as Hard as the Whole. 194-209
• 
  Charles H. Bennett, Gilles Brassard, Jean-Marc Robert: Privacy Amplification by Public Discussion. 210-229
• 
  Benny Chor, Oded Goldreich: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. 230-261
• 
  Alan M. Frieze, Johan Håstad, Ravi Kannan, J. C. Lagarias, Adi Shamir: Reconstructing Truncated Integer Variables Satisfying Linear Congruences. 262-280
• 
  Shafi Goldwasser, Silvio Micali, Ronald L. Rivest: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. 281-308
• 
  Joachim Grollmann, Alan L. Selman: Complexity Measures for Public-Key Cryptosystems. 309-335
• 
  Johan Håstad: Solving Simultaneous Modular Equations of Low Degree. 336-341
• 
  J. C. Lagarias, James A. Reeds: Unique Extrapolation of Polynomial Recurrences. 342-362
• 
  Douglas L. Long, Avi Wigderson: The Discrete Logarithm Hides O(log n) Bits. 363-372
• 
  Michael Luby, Charles Rackoff: How to Construct Pseudorandom Permutations from Pseudorandom Functions. 373-386
• 
  Carl Pomerance, Jeffrey W. Smith, Randy Tuler: A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Algorithm. 387-403
• 
  John H. Reif, J. D. Tygar: Efficient Parallel Pseudorandom Number Generation. 404-411
• 
  Silvio Micali, Charles Rackoff, Bob Sloan: The Notion of Security for Probabilistic Cryptosystems. 412-426

Volume 17, Number 3, June 1988

• 
  Bernard Chazelle: A Functional Approach to Data Structures and Its Use in Multidimensional Searching. 427-462
• 
  Philip N. Klein, John H. Reif: Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM. 463-485
• 
  Xin He, Yaacov Yesha: A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs. 486-491
• 
  Boris Pittel, Jenn-Hwa Yu: On Search Times for Early-Insertion Coalesced Hashing. 492-503
• 
  Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe: Lowness Properties of Sets in the Exponential-Time Hierarchy. 504-516
• 
  Andrew Chi-Chih Yao: Monotone Bipartite Graph Properties are Evasive. 517-520
• 
  Alessandro D'Atri, Marina Moscarini: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination. 521-538
• 
  Dorit S. Hochbaum, David B. Shmoys: A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach. 539-551
• 
  Dan Gusfield: A Graph Theoretic Approach to Statistical Data Security. 552-571
• 
  Pravin M. Vaidya: Minimum Spanning Trees in k-Dimensional Space. 572-582
• 
  Alan Siegel, Danny Dolev: Some Geometry for General River Routing. 583-605
• 
  Faith E. Fich, Prabhakar Ragde, Avi Wigderson: Relations Between Concurrent-Write Models of Parallel Computation. 606-627
• 
  Timothy J. Long: Erratum: On Restricting the Size of Oracles Compared with Restricting Access to Oracles. 628, (see: SIAM J. Comput. 14(3): 585-597 (1985))

Volume 17, Number 4, August 1988

• 
  Nachum Dershowitz, Leo Marcus, Andrzej Tarlecki: Existence, Uniqueness, and Construction of Rewrite Systems. 629-639
• 
  John W. John: A New Lower Bound for the Set-Partitioning Problem. 640-647
• 
  Robert Schaback: On the Expected Sublinearity of the Boyer-Moore Algorithm. 648-658
• 
  Paul M. B. Vitányi: Locality, Communication, and Interconnect Length in Multicomputers. 659-672
• 
  Ludek Kucera, Vera Trnková: Isomorphism Testing of Unary Algebras. 673-686
• 
  Gary L. Miller, Vijaya Ramachandran, Erich Kaltofen: Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits. 687-695
• 
  S. S. Ravi, Errol L. Lloyd: The Complexity of Near-Optimal Programmable Logic Array Folding. 696-710
• 
  Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer: Parallel Algorithms for Term Matching. 711-731
• 
  David Avis, C. W. Lai: The Probabilistic Analysis of a Heuristic for the Assignment Problem. 732-741
• 
  Dan Gusfield: The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments. 742-769
• 
  Richard Cole: Parallel Merge Sort. 770-785
• 
  Etienne Grandjean: A Natural NP-Complete Problem with a Nontrivial Lower Nound. 786-809
• 
  Harold N. Gabow: Scheduling UET Systems on Two Uniform Processors and Length Two Pipelines. 810-829
• 
  Kenneth L. Clarkson: A Randomized Algorithm for Closest-Point Queries. 830-847

Volume 17, Number 5, October 1988

• 
  Mikhail J. Atallah, S. Rao Kosaraju: Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel. 849-869
• 
  Herbert Edelsbrunner, Steven Skiena: Probing Convex Polygons with X-Rays. 870-882
• 
  Richard M. Karp, Rajeev Motwani, Prabhakar Raghavan: Deferred Data Structuring. 883-902
• 
  Ronald V. Book, Ker-I Ko: On Sets Truth-Table Reducible to Sparse Sets. 903-919
• 
  J. Scott Provan: An Approximation Scheme for Finding Steiner Trees with Obstacles. 920-934
• 
  Neil Immerman: Nondeterministic Space is Closed Under Complementation. 935-938
• 
  Stephen L. Bloom, Zoltán Ésik: Varieties of Iteration Theories. 939-966
• 
  Martin E. Dyer, Alan M. Frieze: On the Complexity of Computing the Volume of a Polyhedron. 967-974
• 
  Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal: Fault Tolerance in Networks of Bounded Degree. 975-988
• 
  Alan L. Selman: Natural Self-Reducible Sets. 989-996
• 
  Matthew Hennessy: Axiomatising Finite Concurrent Processes. 997-1017
• 
  Zevi Miller: A Linear Algorithm for Topological Bandwidth in Degree-Three Trees. 1018-1035
• 
  Paolo Zellini: Optimal Bounds for Solving Tridiagonal Systems with Preconditioning. 1036-1043
• 
  Colin McDiarmid: Average-Case Lower Bounds for Searching. 1044-1060
• 
  Robert Endre Tarjan, Christopher J. Van Wyk: Erratum: An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon. 1061

Volume 17, Number 6, December 1988

• 
  Thomas Lengauer, Egon Wanke: Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs. 1063-1080
• 
  Michael Ben-Or, Ephraim Feig, Dexter Kozen, Prasoon Tiwari: A Fast Parallel Algorithm for Determining all Roots of a Polynomial with Real Roots. 1081-1092
• 
  Kurt Mehlhorn, Stefan Näher, Helmut Alt: A Lower Bound on the Complexity of the Union-Split-Find Problem. 1093-1102
• 
  Robert J. T. Morris, Wing Shing Wong: A Short-Term Neural Network Memory. 1103-1118
• 
  Béla Bollobás, Graham Brightwell: Transitive Orientations of Graphs. 1119-1133
• 
  Jan A. Bergstra, Jan Willem Klop, Ernst-Rüdiger Olderog: Readies and Failures in the Algebra of Communicating Processes. 1134-1177
• 
  Noga Alon, Yossi Azar: The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms. 1178-1192
• 
  Eric Allender, Roy S. Rubinstein: P-Printable Sets. 1193-1202
• 
  William J. Knight: Search in an Ordered Array Having Variable Probe Cost. 1203-1214
• 
  T. Yung Kong, David M. Mount, A. W. Roscoe: The Decomposition of a Rectangle into Rectangles of Minimal Perimeter. 1215-1231
• 
  Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung: The Boolean Hierarchy I: Structural Properties. 1232-1252
• 
  Baruch Schieber, Uzi Vishkin: On Finding Lowest Common Ancestors: Simplification and Parallelization. 1253-1262
• 
  Jim Kadin: The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses. 1263-1282, (Erratum: SIAM J. Comput. 20(2): 404 (1991))

last updated on Sat May 18 06:35:42 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page