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 (MOD_p-MOD_m) 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 updated on Tue May 21 03:23:20 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page