Volume 30,
Number 1,
2000
- Richard Cole, Bud Mishra, Jeanette P. Schmidt, Alan Siegel:
On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences.
1-43
- Richard Cole:
On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof.
44-85
- Mikkel Thorup:
On RAM Priority Queues.
86-109
- Dana Angluin, Jeffery Westbrook, Wenhong Zhu:
Robot Navigation with Distance Queries.
110-144
- Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu:
Preemptive Scheduling of Parallel Jobs on Multiprocessors.
145-160
- John H. Reif, Hongyan Wang:
Nonuniform Discretization for Kinodynamic Motion Planning and its Applications.
161-190
- Jon M. Kleinberg, Yuval Rabani, Éva Tardos:
Allocating Bandwidth for Bursty Connections.
191-217
- Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Lazard:
Motion Planning of Legged Robots.
218-246
- Shay Kutten, David Peleg:
Tight Fault Locality.
247-268
- David Greenhalgh, Stephen Marshall:
Convergence Criteria for Genetic Algorithms.
269-282
- Lusheng Wang, Tao Jiang, Dan Gusfield:
A More Efficient Approximation Scheme for Tree Alignment.
283-299
- Elias Koutsoupias, Christos H. Papadimitriou:
Beyond Competitive Analysis.
300-317
- Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou:
On the Difficulty of Designing Good Classifiers.
318-323
- Uriel Feige, Joe Kilian:
Two-Prover Protocols - Low Error at Affordable Rates.
324-346
Volume 30,
Number 2,
2000
- Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
Message Multicasting in Heterogeneous Networks.
347-358
- Clifford Bergman, Giora Slutzki:
Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras.
359-382
- Claudia Bertram-Kretzberg, Thomas Hofmeister, Hanno Lefmann:
An Algorithm for Heilbronn's Problem.
383-390
- Danny Dolev, Cynthia Dwork, Moni Naor:
Nonmalleable Cryptography.
391-437
- Prasad Jayanti, King Tan, Sam Toueg:
Time and Space Lower Bounds for Nonblocking Implementations.
438-456
- Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani:
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.
457-474
- Luca Trevisan:
When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree.
475-485
- George Varghese:
Self-Stabilization by Counter Flushing.
486-510
- Gilad Koren, Emanuel Dar, Amihood Amir:
The Power of Migration in Multiprocessor Scheduling of Real-Time Systems.
511-527
- Joseph Cheriyan, Ramakrishna Thurimella:
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching.
528-560
- Timothy M. Chan:
Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.
561-575
- Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss:
A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem.
576-601
- Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting:
Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees.
602-624
- Andrea Pietracaprina, Geppino Pucci, Jop F. Sibeyn:
Constructive, Deterministic Implementation of Shared Memory on Meshes.
625-648
- Harold N. Gabow, Tibor Jordán:
How to Make a Square Grid Framework with Cables Rigid.
649-680
- Nah-Oak Song, Demosthenis Teneketzis:
On a Conjecture by Coffman, Flatto, and Wright on Stochastic Machine Minimization.
681-687
Volume 30,
Number 3,
2000
- Wai-Kau Lo, Vassos Hadzilacos:
All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust.
689-728
- Bin Ma, Ming Li, Louxin Zhang:
From Gene Trees to Species Trees.
729-752
- Yefim Dinitz, Alek Vainshtein:
The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd Case.
753-808
- Christopher L. Barrett, Riko Jacob, Madhav V. Marathe:
Formal-Language-Constrained Path Problems.
809-837
- Xin He, Ming-Yang Kao, Hsueh-I Lu:
A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs.
838-846
- Sanjiv Kapoor, S. N. Maheshwari:
Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles.
847-871
- Håkan Lennerstad, Lars Lundberg:
Optimal Worst Case Formulas Comparing Cache Memory Associativity.
872-905
- Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan:
Markov Paging.
906-922
- Charles Knessl, Wojciech Szpankowski:
Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme.
923-964
- Haim Kaplan, Chris Okasaki, Robert Endre Tarjan:
Simple Confluently Persistent Catenable Lists.
965-977
- Giri Narasimhan, Michiel H. M. Smid:
Approximating the Stretch Factor of Euclidean Graphs.
978-989
- Manindra Agrawal, Thomas Thierauf:
The Formula Isomorphism Problem.
990-1009
- Peter Bürgisser:
The Computational Complexity to Evaluate Representations of General Linear Groups.
1010-1022
- Peter Bürgisser:
The Computational Complexity of Immanants.
1023-1040
Volume 30,
Number 4,
2000
- Andrzej Czygrinow, Vojtech Rödl:
An Algorithmic Regularity Lemma for Hypergraphs.
1041-1066
- Assaf Natanzon, Ron Shamir, Roded Sharan:
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem.
1067-1079
- Victor Y. Pan:
Parallel Complexity of Computations with General and Toeplitz-Like Matrices Filled with Integers and Extensions.
1080-1125
- Christian Scheideler, Berthold Vöcking:
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols.
1126-1155
- Eric Ruppert:
Determining Consensus Numbers.
1156-1168
- Amir Herzberg, Shay Kutten:
Early Detection of Message Forwarding Faults.
1169-1196
- Jack H. Lutz, Yong Zhao:
The Density of Weakly Complete Problems under Adaptive Reductions.
1197-1210
- Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin:
A Finite State Version of the Kraft--McMillan Theorem.
1211-1230
- Guy Even, Joseph Naor, Leonid Zosin:
An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem.
1231-1252
- Silvio Micali:
Computationally Sound Proofs.
1253-1298
- Vikraman Arvind, Richard Beigel, Antoni Lozano:
The Complexity of Modular Graph Automorphism.
1299-1320
- Kasturi R. Varadarajan, Pankaj K. Agarwal:
Approximating Shortest Paths on a Nonconvex Polyhedron.
1321-1340
- Sariel Har-Peled:
Taking a Walk in a Planar Arrangement.
1341-1367
- Xiaoxu Han, Suely Oliveira, David E. Stewart:
Finding Sets Covering a Point with Application to Mesh-Free Galerkin Methods.
1368-1383
Volume 30,
Number 5,
2000
- Richard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa M. Przytycka, Mikkel Thorup:
An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
1385-1404
- Ruy Luiz Milidiú, Eduardo Sany Laber:
The WARM-UP Algorithm: A Lagrangian Construction of Length Restricted Huffman Codes.
1405-1426
- David Peleg, Vitaly Rubinovich:
A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction.
1427-1442
- Martin E. Dyer, Sandeep Sen:
Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems.
1443-1461
- Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen:
On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems.
1462-1484
- Harry Buhrman, Leen Torenvliet:
Randomness is Hard.
1485-1501
- Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook:
On the Determinization of Weighted Finite Automata.
1502-1531
- Giorgio Gambosi, Alberto Postiglione, Maurizio Talamo:
Algorithms for the Relaxed Online Bin-Packing Model.
1532-1551
- Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson:
Tight Bounds for Searching a Sorted Array of Strings.
1552-1578
- Marcus Brazil, D. A. Thomas, J. F. Weng:
Minimum Networks in Uniform Orientation Metrics.
1579-1593
- Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang:
General Dynamic Routing with Per-Packet Delay Guarantees of O(Distance + 1/Session Rate).
1594-1623
- Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks:
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.
1624-1661
- Andreas Brandstädt, Feodor F. Dragan, Ekkehard Köhler:
Linear Time Algorithms for Hamiltonian Problems on (Claw, Net)-Free Graphs.
1662-1677
- Luc Devroye, Jean Jabbour, Carlos Zamora-Cura:
Squarish k-d Trees.
1678-1700
- Bruno Gaujal, Alain Jean-Marie, Jean Mairesse:
Computations of Uniform Recurrence Equations Using Minimal Memory Size.
1701-1738
Volume 30,
Number 6,
2000
- Pankaj K. Agarwal, Hongyan Wang:
Approximation Algorithms for Curvature-Constrained Shortest Paths.
1739-1772
- Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrto:
On Bipartite Drawings and the Linear Arrangement Problem.
1773-1789
- Alan M. Frieze:
Edge-Disjoint Paths in Expander Graphs.
1790-1801
- Omer Berkman, Michal Parnas, Jiri Sgall:
Efficient Dynamic Traitor Tracing.
1802-1828
- Harry Buhrman, Richard Cleve, Wim van Dam:
Quantum Entanglement and Communication Complexity.
1829-1841
- Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages are Testable with a Constant Number of Queries.
1842-1862
- Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson:
The Approximability of Constraint Satisfaction Problems.
1863-1920
- Waleed Meleis:
Dual-Issue Scheduling for Binary Trees with Spills and Pipelined Loads.
1921-1941
- Tao Jiang, Paul E. Kearney, Ming Li:
A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application.
1942-1961
- Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher:
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings.
1962-1975
- Carlo Mereghetti, Giovanni Pighizzini:
Optimal Simulations between Unary Automata.
1976-1992
- Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
An Approximation Algorithm for Feedback Vertex Sets in Tournaments.
1993-2007
- Daniele Micciancio:
The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.
2008-2035
- Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph.
2036-2050
- Aravind Srinivasan, Chung-Piaw Teo:
A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria.
2051-2068
- Chengbin Chu, Rémy La:
Variable-Sized Bin Packing: Tight Absolute Worst-Case Performance Ratios for Four Approximation Algorithms.
2069-2083
- Grazyna Mirkowska, Andrzej Salwicki, Marian Srebrny, Andrzej Tarlecki:
First-Order Specifications of Programmable Data Types.
2084-2096
Copyright © Mon Nov 2 21:51:48 2009
by Michael Ley (ley@uni-trier.de)
