SIAM Journal on Computing, Volume 17

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 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