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 updated on Sat May 18 06:35:43 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page