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
- 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
- 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
- Johan Håstad: Solving Simultaneous Modular Equations of Low Degree. 336-341
- 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
- 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
- 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
- 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
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
- 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
- J. Scott Provan: An Approximation Scheme for Finding Steiner Trees with Obstacles. 920-934
- Neil Immerman: Nondeterministic Space is Closed Under Complementation. 935-938
- 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
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-17T203624 by the dblp team