Volume 25, Number 1, February 1996
- Adam J. Grove, Joseph Y. Halpern, Daphne Koller:
Asymptotic Conditional Probabilities: The Unary Case.
1-51 BibTeX
- Yijie Han:
A Fast Derandomization Scheme and Its Applications.
52-82 BibTeX
- Richa Agarwala, David Fernández-Baca:
Weighted Multidimensional Search and Its Application to Convex Optimization.
83-99 BibTeX
- Pankaj K. Agarwal, Micha Sharir:
Ray Shooting amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions.
100-116 BibTeX
- Bruce M. Kapron, Steven A. Cook:
A New Characterization of Type-2 Feasibility.
117-132 BibTeX
- Kenneth W. Regan:
Linear Time and Memory-Efficient Computation.
133-168 BibTeX
- Oded Goldreich, Hugo Krawczyk:
On the Composition of Zero-Knowledge Proof Systems.
169-192 BibTeX
- Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
The Isomorphism Conjecture Holds Relative to an Oracle.
193-206 BibTeX
- 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 BibTeX
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 BibTeX
- Ronitt Rubinfeld, Madhu Sudan:
Robust Characterizations of Polynomials with Applications to Program Testing.
252-271 BibTeX
- Vineet Bafna, Pavel A. Pevzner:
Genome Rearrangements and Sorting by Reversals.
272-289 BibTeX
- 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 BibTeX
- Michael D. Hutton, Anna Lubiw:
Upward Planning of Single-Source Acyclic Digraphs.
291-311 BibTeX
- Vijaya Ramachandran, Honghua Yang:
An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem.
312-339 BibTeX
- Richard Chang, Jim Kadin:
The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection.
340-354 BibTeX
- Samir Khuller, Balaji Raghavachari, Neal E. Young:
Low-Degree Spanning Trees of Small Weight.
355-368 BibTeX
- Hagit Attiya, Amir Herzberg, Sergio Rajsbaum:
Optimal Clock Synchronization under Different Delay Assumptions.
369-389 BibTeX
- Xiaotie Deng, Pavol Hell, Jing Huang:
Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs.
390-403 BibTeX
- 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 BibTeX
- Anmol Mathur, Edward M. Reingold:
Generalized Kraft's Inequality and Discrete k-Modal Search.
420-447 BibTeX
- Richard Edwin Stearns, Harry B. Hunt III:
An Algebraic Model for Combinatorial Problems.
448-476 BibTeX
Volume 25, Number 3, June 1996
- Sandy Irani, Anna R. Karlin, Steven Phillips:
Strongly Competitive Algorithms for Paging with Locality of Reference.
477-497 BibTeX
- Sandy Irani, Yuval Rabani:
On the Value of Coordination in Distributed Decision Making.
498-519 BibTeX
- Anne Condon, Richard E. Ladner, Jordan Lampe, Rakesh K. Sinha:
Complexity of Sub-Bus Mesh Computations.
520-539 BibTeX
- Haim Kaplan, Ron Shamir:
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques.
540-561 BibTeX
- Joseph Friedman, John Hershberger, Jack Snoeyink:
Efficiently Planning Compliant Motion in the Plane.
562-599 BibTeX
- Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs:
On-Line Algorithms for Path Selection in a Nonblocking Network.
600-625 BibTeX
- Lefteris M. Kirousis, Dimitrios M. Thilikos:
The Linkage of a Graph.
626-647 BibTeX
- Sampath Kannan, Eugene W. Myers:
An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score.
648-662 BibTeX
- Trevor Jim, Albert R. Meyer:
Full Abstraction and the Context Lemma.
663-696 BibTeX
Volume 25, Number 4, August 1996
Volume 25,
Number 5,
October 1996
- Zvi Galil, Kunsoo Park:
Alphabet-Independent Two-Dimensional Witness Computation.
907-935 BibTeX
- Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson:
The Tree Model for Hashing: Lower and Upper Bounds.
936-955 BibTeX
- Giuseppe Di Battista, Roberto Tamassia:
On-Line Planarity Testing.
956-997 BibTeX
- Zvi M. Kedem, Gad M. Landau, Krishna V. Palem:
Parallel Suffix-Prefix-Matching Algorithm and Applications.
998-1023 BibTeX
- James Aspnes, Orli Waarts:
Randomized Consensus in Expected O(n log² n) Operations Per Processor.
1024-1044 BibTeX
- Satoshi Fujita, Masafumi Yamashita:
Optimal Group Gossiping in Hypercubes under a Circuit-Switching Model.
1045-1060 BibTeX
- Marco Pellegrini:
On Point Location and Motion Planning among Simplices.
1061-1081 BibTeX
- Robert Cypher, Smaragda Konstantinidou:
Bounds on the Efficiency of Message-Passing Protocols for Parallel Computers.
1082-1104 BibTeX
- Wei Kuan Shih, Jane W.-S. Liu:
On-Line Scheduling of Imprecise Computations to Minimize Error.
1105-1121 BibTeX
Volume 25,
Number 6,
December 1996
- Martin Kummer:
Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets.
1123-1143 BibTeX
- Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn:
An o(n³)-Time Algorithm Maximum-Flow Algorithm.
1144-1170 BibTeX
- Miklós Ajtai, Nimrod Megiddo:
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions.
1171-1195 BibTeX
- Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk:
Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines.
1196-123 BibTeX
- Jürgen Sellen:
Lower Bounds for Geometrical and Physical Problems.
1231-1253 BibTeX
- Nechama Allenberg-Navony, Alon Itai, Shlomo Moran:
Average and Randomized Complexity of Distributed Problems.
1254-1267 BibTeX
- Francesco Bergadano, Stefano Varricchio:
Learning Behaviors of Automata from Multiplicity and Equivalence Queries.
1268-1280 BibTeX
- Mordecai J. Golin, Neal E. Young:
Prefix Codes: Equiprobable Words, Unequal Letter Costs.
1281-1292 BibTeX
- David Zuckerman:
On Unapproximable Versions of NP-Complete Problems.
1293-1304 BibTeX
- Hans L. Bodlaender:
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth.
1305-1317 BibTeX
- Alberto Apostolico, Dany Breslauer:
An Optimal O(log log N)-Time Parallel Algorithm for Detecting All Squares in a String.
1318-1331 BibTeX
- Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld:
The Wakeup Problem.
1331-1332 BibTeX
- Dario Bini, Luca Gemignani:
Erratum: Fast Parallel Computation of the Polynomial Remainder Sequence via Bezout and Hankel Matrices.
1358 BibTeX
Copyright © Sun May 17 00:18:54 2009
by Michael Ley (ley@uni-trier.de)