SIAM Journal on Computing, Volume 30

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 BibTeX
• Richard Cole: On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof. 44-85 BibTeX
• Mikkel Thorup: On RAM Priority Queues. 86-109 BibTeX
• Dana Angluin, Jeffery Westbrook, Wenhong Zhu: Robot Navigation with Distance Queries. 110-144 BibTeX
• Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu: Preemptive Scheduling of Parallel Jobs on Multiprocessors. 145-160 BibTeX
• John H. Reif, Hongyan Wang: Nonuniform Discretization for Kinodynamic Motion Planning and its Applications. 161-190 BibTeX
• Jon M. Kleinberg, Yuval Rabani, Éva Tardos: Allocating Bandwidth for Bursty Connections. 191-217 BibTeX
• Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Lazard: Motion Planning of Legged Robots. 218-246 BibTeX
• Shay Kutten, David Peleg: Tight Fault Locality. 247-268 BibTeX
• David Greenhalgh, Stephen Marshall: Convergence Criteria for Genetic Algorithms. 269-282 BibTeX
• Lusheng Wang, Tao Jiang, Dan Gusfield: A More Efficient Approximation Scheme for Tree Alignment. 283-299 BibTeX
• Elias Koutsoupias, Christos H. Papadimitriou: Beyond Competitive Analysis. 300-317 BibTeX
• Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou: On the Difficulty of Designing Good Classifiers. 318-323 BibTeX
• Uriel Feige, Joe Kilian: Two-Prover Protocols - Low Error at Affordable Rates. 324-346 BibTeX

Volume 30, Number 2, 2000

• Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Message Multicasting in Heterogeneous Networks. 347-358 BibTeX
• Clifford Bergman, Giora Slutzki: Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras. 359-382 BibTeX
• Claudia Bertram-Kretzberg, Thomas Hofmeister, Hanno Lefmann: An Algorithm for Heilbronn's Problem. 383-390 BibTeX
• Danny Dolev, Cynthia Dwork, Moni Naor: Nonmalleable Cryptography. 391-437 BibTeX
• Prasad Jayanti, King Tan, Sam Toueg: Time and Space Lower Bounds for Nonblocking Implementations. 438-456 BibTeX
• Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. 457-474 BibTeX
• Luca Trevisan: When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. 475-485 BibTeX
• George Varghese: Self-Stabilization by Counter Flushing. 486-510 BibTeX
• Gilad Koren, Emanuel Dar, Amihood Amir: The Power of Migration in Multiprocessor Scheduling of Real-Time Systems. 511-527 BibTeX
• Joseph Cheriyan, Ramakrishna Thurimella: Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. 528-560 BibTeX
• Timothy M. Chan: Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. 561-575 BibTeX
• 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 BibTeX
• Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting: Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees. 602-624 BibTeX
• Andrea Pietracaprina, Geppino Pucci, Jop F. Sibeyn: Constructive, Deterministic Implementation of Shared Memory on Meshes. 625-648 BibTeX
• Harold N. Gabow, Tibor Jordán: How to Make a Square Grid Framework with Cables Rigid. 649-680 BibTeX
• Nah-Oak Song, Demosthenis Teneketzis: On a Conjecture by Coffman, Flatto, and Wright on Stochastic Machine Minimization. 681-687 BibTeX

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
  Electronic Edition (link) BibTeX
• Bin Ma, Ming Li, Louxin Zhang:
  From Gene Trees to Species Trees. 729-752
  Electronic Edition (link) BibTeX
• 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
  Electronic Edition (link) BibTeX
• Christopher L. Barrett, Riko Jacob, Madhav V. Marathe:
  Formal-Language-Constrained Path Problems. 809-837
  Electronic Edition (link) BibTeX
• Xin He, Ming-Yang Kao, Hsueh-I Lu:
  A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs. 838-846
  Electronic Edition (link) BibTeX
• Sanjiv Kapoor, S. N. Maheshwari:
  Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles. 847-871
  Electronic Edition (link) BibTeX
• Håkan Lennerstad, Lars Lundberg:
  Optimal Worst Case Formulas Comparing Cache Memory Associativity. 872-905
  Electronic Edition (link) BibTeX
• Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan:
  Markov Paging. 906-922
  Electronic Edition (link) BibTeX
• 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
  Electronic Edition (link) BibTeX
• Haim Kaplan, Chris Okasaki, Robert Endre Tarjan:
  Simple Confluently Persistent Catenable Lists. 965-977
  Electronic Edition (link) BibTeX
• Giri Narasimhan, Michiel H. M. Smid:
  Approximating the Stretch Factor of Euclidean Graphs. 978-989
  Electronic Edition (link) BibTeX
• Manindra Agrawal, Thomas Thierauf:
  The Formula Isomorphism Problem. 990-1009
  Electronic Edition (link) BibTeX
• Peter Bürgisser:
  The Computational Complexity to Evaluate Representations of General Linear Groups. 1010-1022
  Electronic Edition (link) BibTeX
• Peter Bürgisser:
  The Computational Complexity of Immanants. 1023-1040
  Electronic Edition (link) BibTeX

Volume 30, Number 4, 2000

• Andrzej Czygrinow, Vojtech Rödl:
  An Algorithmic Regularity Lemma for Hypergraphs. 1041-1066
  Electronic Edition (link) BibTeX
• Assaf Natanzon, Ron Shamir, Roded Sharan:
  A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. 1067-1079
  Electronic Edition (link) BibTeX
• Victor Y. Pan:
  Parallel Complexity of Computations with General and Toeplitz-Like Matrices Filled with Integers and Extensions. 1080-1125
  Electronic Edition (link) BibTeX
• Christian Scheideler, Berthold Vöcking:
  From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. 1126-1155
  Electronic Edition (link) BibTeX
• Eric Ruppert:
  Determining Consensus Numbers. 1156-1168
  Electronic Edition (link) BibTeX
• Amir Herzberg, Shay Kutten:
  Early Detection of Message Forwarding Faults. 1169-1196
  Electronic Edition (link) BibTeX
• Jack H. Lutz, Yong Zhao:
  The Density of Weakly Complete Problems under Adaptive Reductions. 1197-1210
  Electronic Edition (link) BibTeX
• Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin:
  A Finite State Version of the Kraft--McMillan Theorem. 1211-1230
  Electronic Edition (link) BibTeX
• Guy Even, Joseph Naor, Leonid Zosin:
  An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem. 1231-1252
  Electronic Edition (link) BibTeX
• Silvio Micali:
  Computationally Sound Proofs. 1253-1298
  Electronic Edition (link) BibTeX
• Vikraman Arvind, Richard Beigel, Antoni Lozano:
  The Complexity of Modular Graph Automorphism. 1299-1320
  Electronic Edition (link) BibTeX
• Kasturi R. Varadarajan, Pankaj K. Agarwal:
  Approximating Shortest Paths on a Nonconvex Polyhedron. 1321-1340
  Electronic Edition (link) BibTeX
• Sariel Har-Peled:
  Taking a Walk in a Planar Arrangement. 1341-1367
  Electronic Edition (link) BibTeX
• Xiaoxu Han, Suely Oliveira, David E. Stewart:
  Finding Sets Covering a Point with Application to Mesh-Free Galerkin Methods. 1368-1383
  Electronic Edition (link) BibTeX

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
  Electronic Edition (link) BibTeX
• Ruy Luiz Milidiú, Eduardo Sany Laber:
  The WARM-UP Algorithm: A Lagrangian Construction of Length Restricted Huffman Codes. 1405-1426
  Electronic Edition (link) BibTeX
• David Peleg, Vitaly Rubinovich:
  A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. 1427-1442
  Electronic Edition (link) BibTeX
• Martin E. Dyer, Sandeep Sen:
  Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems. 1443-1461
  Electronic Edition (link) BibTeX
• Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen:
  On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems. 1462-1484
  Electronic Edition (link) BibTeX
• Harry Buhrman, Leen Torenvliet:
  Randomness is Hard. 1485-1501
  Electronic Edition (link) BibTeX
• Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook:
  On the Determinization of Weighted Finite Automata. 1502-1531
  Electronic Edition (link) BibTeX
• Giorgio Gambosi, Alberto Postiglione, Maurizio Talamo:
  Algorithms for the Relaxed Online Bin-Packing Model. 1532-1551
  Electronic Edition (link) BibTeX
• Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson:
  Tight Bounds for Searching a Sorted Array of Strings. 1552-1578
  Electronic Edition (link) BibTeX
• Marcus Brazil, D. A. Thomas, J. F. Weng:
  Minimum Networks in Uniform Orientation Metrics. 1579-1593
  Electronic Edition (link) BibTeX
• 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
  Electronic Edition (link) BibTeX
• Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks:
  A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems. 1624-1661
  Electronic Edition (link) BibTeX
• Andreas Brandstädt, Feodor F. Dragan, Ekkehard Köhler:
  Linear Time Algorithms for Hamiltonian Problems on (Claw, Net)-Free Graphs. 1662-1677
  Electronic Edition (link) BibTeX
• Luc Devroye, Jean Jabbour, Carlos Zamora-Cura:
  Squarish k-d Trees. 1678-1700
  Electronic Edition (link) BibTeX
• Bruno Gaujal, Alain Jean-Marie, Jean Mairesse:
  Computations of Uniform Recurrence Equations Using Minimal Memory Size. 1701-1738
  Electronic Edition (link) BibTeX

Volume 30, Number 6, 2000

• Pankaj K. Agarwal, Hongyan Wang:
  Approximation Algorithms for Curvature-Constrained Shortest Paths. 1739-1772
  Electronic Edition (link) BibTeX
• Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrto:
  On Bipartite Drawings and the Linear Arrangement Problem. 1773-1789
  Electronic Edition (link) BibTeX
• Alan M. Frieze:
  Edge-Disjoint Paths in Expander Graphs. 1790-1801
  Electronic Edition (link) BibTeX
• Omer Berkman, Michal Parnas, Jiri Sgall:
  Efficient Dynamic Traitor Tracing. 1802-1828
  Electronic Edition (link) BibTeX
• Harry Buhrman, Richard Cleve, Wim van Dam:
  Quantum Entanglement and Communication Complexity. 1829-1841
  Electronic Edition (link) BibTeX
• Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
  Regular Languages are Testable with a Constant Number of Queries. 1842-1862
  Electronic Edition (link) BibTeX
• Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson:
  The Approximability of Constraint Satisfaction Problems. 1863-1920
  Electronic Edition (link) BibTeX
• Waleed Meleis:
  Dual-Issue Scheduling for Binary Trees with Spills and Pipelined Loads. 1921-1941
  Electronic Edition (link) BibTeX
• Tao Jiang, Paul E. Kearney, Ming Li:
  A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application. 1942-1961
  Electronic Edition (link) BibTeX
• 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
  Electronic Edition (link) BibTeX
• Carlo Mereghetti, Giovanni Pighizzini:
  Optimal Simulations between Unary Automata. 1976-1992
  Electronic Edition (link) BibTeX
• Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
  An Approximation Algorithm for Feedback Vertex Sets in Tournaments. 1993-2007
  Electronic Edition (link) BibTeX
• Daniele Micciancio:
  The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant. 2008-2035
  Electronic Edition (link) BibTeX
• Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
  Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph. 2036-2050
  Electronic Edition (link) BibTeX
• Aravind Srinivasan, Chung-Piaw Teo:
  A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria. 2051-2068
  Electronic Edition (link) BibTeX
• Chengbin Chu, Rémy La:
  Variable-Sized Bin Packing: Tight Absolute Worst-Case Performance Ratios for Four Approximation Algorithms. 2069-2083
  Electronic Edition (link) BibTeX
• Grazyna Mirkowska, Andrzej Salwicki, Marian Srebrny, Andrzej Tarlecki:
  First-Order Specifications of Programmable Data Types. 2084-2096
  Electronic Edition (link) BibTeX