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
  
• 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, Doreen A. Thomas, Jia 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
  

Last update Sat May 26 07:00:38 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page