Volume 29, Number 1, September 1999
- Uriel Feige, Dror Lapidot, Adi Shamir:
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions.
1-28

- Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman:
Tight Analyses of Two Local Load Balancing Algorithms.
29-64

- Xin He, Zhi-Zhong Chen:
An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications.
65-80

- Eberhard Bertsch, Mark-Jan Nederhof:
Regular Closure of Deterministic Languages.
81-102

- Maria Luisa Bonet, Cynthia A. Phillips, Tandy Warnow, Shibu Yooseph:
Constructing Evolutionary Trees in the Presence of Polymorphic Characters.
103-131

- E. Allen Emerson, Charanjit S. Jutla:
The Complexity of Tree Automata and Logics of Programs.
132-158

- Naveen Garg, Huzur Saran, Vijay V. Vazirani:
Finding Separator Cuts in Planar Graphs within Twice the Optimal.
159-179

- Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal:
Balanced Allocations.
180-200

- Claudia Bertram-Kretzberg, Hanno Lefmann:
The Algorithmic Aspects of Uncrowded Hypergraphs.
201-230

- Jerzy Marcinkowski:
Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs.
231-257

- Frank Thomson Leighton, Yuan Ma:
Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults.
258-273

- Tibor Szkaliczki:
Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is NP-Complete.
274-287

- Weimin Chen, Volker Turau:
On Regular Tree Embeddings.
288-301

- Josef M. Breutzmann, Jack H. Lutz:
Equivalence of Measures of Complexity Classes.
302-326

- Shoshana Anily, Michel Gendreau, Gilbert Laporte:
The Swapping Problem on a Line.
327-335

- Howard J. Karloff:
How Good is the Goemans-Williamson MAX CUT Algorithm?
336-350

Volume 29, Number 2, October-December 1999
- Benny Chor, Lee-Bath Nelson:
Solvability in Asynchronous Environments II: Finite Interactive Tasks.
351-377

- Elaine M. Eschen, Ryan Hayward, Jeremy Spinrad, R. Sritharan:
Weakly Triangulated Comparability Graphs.
378-386

- Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum:
On Approximately Counting Colorings of Small Degree Graphs.
387-400

- Stephen J. Bellantoni, Karl-Heinz Niggl:
Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited.
401-415

- Michael T. Goodrich:
Communication-Efficient Parallel Sorting.
416-432

- J. H. Rieger:
Proximity in Arrangements of Algebraic Sets.
433-458

- Susanne Albers:
Better Bounds for Online Scheduling.
459-473

- Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu:
Tight Bounds for On-Line Tree Embeddings.
474-491

- David R. Karger:
A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem.
492-514

- Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven Skiena, Tae-Cheon Yang:
On the Maximum Scatter Traveling Salesperson Problem.
515-544

- Rodney G. Downey, Michael R. Fellows, Alexander Vardy, Geoff Whittle:
The Parametrized Complexity of Some Fundamental Problems in Coding Theory.
545-570

- Juha Kärkkäinen, Esko Ukkonen:
Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time.
571-589

- Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi:
Kolmogorov Random Graphs and the Incompressibility Method.
590-599

- Steven C. Bruell, Sukumar Ghosh, Mehmet Hakan Karaata, Sriram V. Pemmaraju:
Self-Stabilizing Algorithms for Finding Centers and Medians of Trees.
600-614

- Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang:
Automatic Methods for Hiding Latency in Parallel and Distributed Computation.
615-647

- Aravind Srinivasan:
Improved Approximation Guarantees for Packing and Covering Integer Programs.
648-670

- Frank Ruskey, Joe Sawada:
An Efficient Algorithm for Generating Necklaces with Fixed Density.
671-684

- Zhivko Prodanov Nedev:
Finding an Even Simple Path in a Directed Planar Graph.
685-695

Volume 29, Number 3, December 1999
- Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber:
The Angular-Metric Traveling Salesman Problem.
697-711

- B. Natarajan:
On Learning Functions from Noise-Free and Noisy Samples via Occam's Razor.
712-727

- Mark Levene, George Loizou:
Navigation in Hypertext Is Easy Only Sometimes.
728-760

- Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang:
A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees.
761-778

- Paolo Boldi, Sebastiano Vigna:
Complexity of Deciding Sense of Direction.
779-789

- Amos Fiat, Moni Naor:
Rigorous Time/Space Trade-offs for Inverting Functions.
790-803

- Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg:
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks.
804-833

- Leslie Ann Goldberg, Mark Jerrum:
Randomly Sampling Molecules.
834-853

- Scott E. Decatur, Oded Goldreich, Dana Ron:
Computational Sample Complexity.
854-879

- Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals.
880-892

- S. Rao Kosaraju, Giovanni Manzini:
Compression of Low Entropy Strings with Lempel-Ziv Algorithms.
893-911

- Pankaj K. Agarwal, Alon Efrat, Micha Sharir:
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications.
912-953

- Z. Sweedyk:
A 2½-Approximation Algorithm for Shortest Superstring.
954-986

- Ioan I. Macarie:
On the Structure of Logspace Probabilistic Complexity Classes.
987-1007

- Flávio Keidi Miyazawa, Yoshiko Wakabayashi:
Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem.
1008-1029

Volume 29, Number 3, January 2000
- Dan E. Willard:
Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree.
1030-1049

Volume 29, Number 4, 2000
- Tracy Kimbrel, Anna R. Karlin:
Near-Optimal Parallel Prefetching and Caching.
1051-1082

- Leszek Pacholski, Wieslaw Szwast, Lidia Tendera:
Complexity Results for First-Order Two-Variable Logic with Counting.
1083-1117

- Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous.
1118-1131

- Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
1132-1154

- Sridhar Rajagopalan, Leonard J. Schulman:
Verification of Identities.
1155-1163

- Susanne Albers, Monika Rauch Henzinger:
Exploring Unknown Environments.
1164-1188

- Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky:
Reducibility and Completeness in Private Computations.
1189-1208

- Vince Grolmusz, Gábor Tardos:
Lower Bounds for (MODp-MODm) Circuits.
1209-1222

- Danny Z. Chen, Kevin S. Klenk, Hung-Yi Tu:
Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane.
1223-1246

- Zhi-Zhong Chen, Ming-Yang Kao:
Reducing Randomness via Irrational Numbers.
1247-1256

- Wei-Liang Lin, Amir H. Farrahi, Majid Sarrafzadeh:
On the Power of Logic Resynthesis.
1257-1289

- Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter:
Application-Controlled Paging for a Shared Cache.
1290-1303

- Ravi B. Boppana, Babu O. Narayanan:
Perfect-Information Leader Election with Optimal Resilience.
1304-1320

- Alok Aggarwal, Jon M. Kleinberg, David P. Williamson:
Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout.
1321-1333

- Scott A. Mitchell, Stephen A. Vavasis:
Quality Mesh Generation in Higher Dimensions.
1334-1370

- Edward P. F. Chan, Ron van der Meyden:
Containment and Optimization of Object-Preserving Conjunctive Queries.
1371-1400

Volume 29, Number 5, 2000
- Jean-Daniel Boissonnat, Franco P. Preparata:
Robust Plane Sweep for Intersecting Segments.
1401-1421

- Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter:
Binary Space Partitions for Fat Rectangles.
1422-1448

- Michael E. Saks, Fotios Zaharoglou:
Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge.
1449-1483

- Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross:
An Optimal Algorithm for Monte Carlo Estimation.
1484-1496

- Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet:
Separating Complexity Classes Using Autoreducibility.
1497-1520

- Johannes A. La Poutré:
Maintenance of 2- and 3-Edge-Connected Components of Graphs II.
1521-1549

- Millist W. Vincent, Mark Levene:
Restructuring Partitioned Normal Form Relations without Information Loss.
1550-1567

- Ming-Yang Kao, Jie Wang:
Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors.
1568-1576

- Jürgen Sellen, Joonsoo Choi, Chee-Keng Yap:
Precision-Sensitive Euclidean Shortest Path in 3-Space.
1577-1595

- Oren Etzioni, Steve Hanks, Tao Jiang, Omid Madani:
Optimal Information Gathering on the Internet with Time and Cost Constraints.
1596-1620

- Ladislav Stacho, Imrich Vrto:
Virtual Path Layouts in ATM Networks.
1621-1629

- Funda Ergün, Ravi Kumar, D. Sivakumar:
Self-Testing without the Generator Bottleneck.
1630-1651

- Michael Benedikt, Leonid Libkin:
Safe Constraint Queries.
1652-1682

- Sanjeev Khanna, Vincenzo Liberatore:
On Broadcast Disk Paging.
1683-1702

- Artur Czumaj, Friedhelm Meyer auf der Heide, Volker Stemann:
Contention Resolution in Hashing Based Shared Memory Simulations.
1703-1739

- Dorit Dor, Shay Halperin, Uri Zwick:
All-Pairs Almost Shortest Paths.
1740-1759

Volume 29, Number 6, 2000
- Monika Rauch Henzinger:
Improved Data Structures for Fully Dynamic Biconnectivity.
1761-1815

- Håkan Lennerstad, Lars Lundberg:
Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems.
1816-1838

- Joachim von zur Gathen, Igor Shparlinski:
The CREW PRAM Complexity of Modular Inversion.
1839-1857

- Sanjiv Kapoor:
Dynamic Maintenance of Maxima of 2-d Point Sets.
1858-1877

- Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein:
The Complexity of the A B C Problem.
1878-1888

- Dahlia Malkhi, Michael K. Reiter, Avishai Wool:
The Load and Availability of Byzantine Quorum Systems.
1889-1906

- Avrim Blum, Prasad Chalasani:
An Online Algorithm for Improving Performance in Navigation.
1907-1938

- Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
On Interpolation and Automatization for Frege Systems.
1939-1967

- Jeff Erickson:
Space-Time Tradeoffs for Emptiness Queries.
1968-1996

- Micah Adler, John W. Byers, Richard M. Karp:
Parallel Sorting with Limited Bandwidth.
1997-2015

- Sariel Har-Peled:
Constructing Planar Cuttings in Theory and Practice.
2016-2039

- Marcos Kawazoe Aguilera, Wei Chen, Sam Toueg:
On Quiescent Reliable Communication.
2040-2073

- Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
Gadgets, Approximation, and Linear Programming.
2074-2097

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