SIAM Journal on Computing, Volume 25

Volume 25, Number 1, February 1996

• Adam J. Grove, Joseph Y. Halpern, Daphne Koller:
  Asymptotic Conditional Probabilities: The Unary Case. 1-51
  
• Yijie Han:
  A Fast Derandomization Scheme and Its Applications. 52-82
  
• Richa Agarwala, David Fernández-Baca:
  Weighted Multidimensional Search and Its Application to Convex Optimization. 83-99
  
• Pankaj K. Agarwal, Micha Sharir:
  Ray Shooting amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions. 100-116
  
• Bruce M. Kapron, Stephen A. Cook:
  A New Characterization of Type-2 Feasibility. 117-132
  
• Kenneth W. Regan:
  Linear Time and Memory-Efficient Computation. 133-168
  
• Oded Goldreich, Hugo Krawczyk:
  On the Composition of Zero-Knowledge Proof Systems. 169-192
  
• Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
  The Isomorphism Conjecture Holds Relative to an Oracle. 193-206
  
• Yi-Jen Chiang, Franco P. Preparata, Roberto Tamassia:
  A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps. 207-233
  

Volume 25, Number 2, April 1996

• Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis:
  Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications. 235-251
  
• Ronitt Rubinfeld, Madhu Sudan:
  Robust Characterizations of Polynomials with Applications to Program Testing. 252-271
  
• Vineet Bafna, Pavel A. Pevzner:
  Genome Rearrangements and Sorting by Reversals. 272-289
  
• Appajosyula Satyanarayana, R. Kevin Wood, L. Camarinopoulos, G. Pampoukis:
  Note on "A Linear-Time Algorithm for Computing K-Terminal Reliability in a Series-Parallel Network". 290
  
• Michael D. Hutton, Anna Lubiw:
  Upward Planning of Single-Source Acyclic Digraphs. 291-311
  
• Vijaya Ramachandran, Honghua Yang:
  An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem. 312-339
  
• Richard Chang, Jim Kadin:
  The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection. 340-354
  
• Samir Khuller, Balaji Raghavachari, Neal E. Young:
  Low-Degree Spanning Trees of Small Weight. 355-368
  
• Hagit Attiya, Amir Herzberg, Sergio Rajsbaum:
  Optimal Clock Synchronization under Different Delay Assumptions. 369-389
  
• Xiaotie Deng, Pavol Hell, Jing Huang:
  Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs. 390-403
  
• Chong Jye Rhee, Y. Daniel Liang, Sudarshan K. Dhall, S. Lakshmivarahan:
  An O(N+M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph. 404-419
  
• Anmol Mathur, Edward M. Reingold:
  Generalized Kraft's Inequality and Discrete k-Modal Search. 420-447
  
• Richard Edwin Stearns, Harry B. Hunt III:
  An Algebraic Model for Combinatorial Problems. 448-476
  

Volume 25, Number 3, June 1996

• Sandy Irani, Anna R. Karlin, Steven Phillips:
  Strongly Competitive Algorithms for Paging with Locality of Reference. 477-497
  
• Sandy Irani, Yuval Rabani:
  On the Value of Coordination in Distributed Decision Making. 498-519
  
• Anne Condon, Richard E. Ladner, Jordan Lampe, Rakesh K. Sinha:
  Complexity of Sub-Bus Mesh Computations. 520-539
  
• Haim Kaplan, Ron Shamir:
  Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques. 540-561
  
• Joseph Friedman, John Hershberger, Jack Snoeyink:
  Efficiently Planning Compliant Motion in the Plane. 562-599
  
• Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs:
  On-Line Algorithms for Path Selection in a Nonblocking Network. 600-625
  
• Lefteris M. Kirousis, Dimitrios M. Thilikos:
  The Linkage of a Graph. 626-647
  
• Sampath Kannan, Eugene W. Myers:
  An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score. 648-662
  
• Trevor Jim, Albert R. Meyer:
  Full Abstraction and the Context Lemma. 663-696
  

Volume 25, Number 4, August 1996

• Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman:
  Computing Solutions Uniquely Collapses the Polynomial Hierarchy. 697-708
  
• Shuji Jimbo, Akira Maruoka:
  A Method of Constructing Selection Networks with O(log n) Depth. 709-739
  
• Johan Håstad, Frank Thomson Leighton, Brian Rogoff:
  Analysis of Backoff Protocols for Multiple Access Channels. 740-774
  
• Sanjiv Kapoor, Michiel H. M. Smid:
  New Techniques for Exact and Approximate Dynamic Closest-Point Problems. 775-796
  
• Philip N. Klein:
  Efficient Parallel Algorithms for Chordal Graphs. 797-827
  
• Maciej Liskiewicz, Rüdiger Reischuk:
  The Sublogarithmic Alternating Space World. 828-861
  
• Sanguthevar Rajasekaran:
  Tree-Adjoining Language Parsing in o(n^6) Time. 862-873
  
• Prakesh Ramanan:
  An Efficient Parallel Algorithm for the Martix-Chain-Product Problem. 874-893
  
• Wansoo T. Rhee, Michel Talagrand:
  Convergence in Distribution for Best-Fit Decreasing. 894-906
  

Volume 25, Number 5, October 1996

• Zvi Galil, Kunsoo Park:
  Alphabet-Independent Two-Dimensional Witness Computation. 907-935
  
• Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson:
  The Tree Model for Hashing: Lower and Upper Bounds. 936-955
  
• Giuseppe Di Battista, Roberto Tamassia:
  On-Line Planarity Testing. 956-997
  
• Zvi M. Kedem, Gad M. Landau, Krishna V. Palem:
  Parallel Suffix-Prefix-Matching Algorithm and Applications. 998-1023
  
• James Aspnes, Orli Waarts:
  Randomized Consensus in Expected O(n log² n) Operations Per Processor. 1024-1044
  
• Satoshi Fujita, Masafumi Yamashita:
  Optimal Group Gossiping in Hypercubes under a Circuit-Switching Model. 1045-1060
  
• Marco Pellegrini:
  On Point Location and Motion Planning among Simplices. 1061-1081
  
• Robert Cypher, Smaragda Konstantinidou:
  Bounds on the Efficiency of Message-Passing Protocols for Parallel Computers. 1082-1104
  
• Wei-Kuan Shih, Jane W.-S. Liu:
  On-Line Scheduling of Imprecise Computations to Minimize Error. 1105-1121
  

Volume 25, Number 6, December 1996

• Martin Kummer:
  Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets. 1123-1143
  
• Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn:
  An o(n³)-Time Algorithm Maximum-Flow Algorithm. 1144-1170
  
• Miklós Ajtai, Nimrod Megiddo:
  A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions. 1171-1195
  
• Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk:
  Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines. 1196-123
  
• Jürgen Sellen:
  Lower Bounds for Geometrical and Physical Problems. 1231-1253
  
• Nechama Allenberg-Navony, Alon Itai, Shlomo Moran:
  Average and Randomized Complexity of Distributed Problems. 1254-1267
  
• Francesco Bergadano, Stefano Varricchio:
  Learning Behaviors of Automata from Multiplicity and Equivalence Queries. 1268-1280
  
• Mordecai J. Golin, Neal E. Young:
  Prefix Codes: Equiprobable Words, Unequal Letter Costs. 1281-1292
  
• David Zuckerman:
  On Unapproximable Versions of NP-Complete Problems. 1293-1304
  
• Hans L. Bodlaender:
  A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. 1305-1317
  
• Alberto Apostolico, Dany Breslauer:
  An Optimal O(log log N)-Time Parallel Algorithm for Detecting All Squares in a String. 1318-1331
  
• Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld:
  The Wakeup Problem. 1331-1332
  
• Dario Bini, Luca Gemignani:
  Erratum: Fast Parallel Computation of the Polynomial Remainder Sequence via Bezout and Hankel Matrices. 1358
  

Last update Sat May 18 20:52:32 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page