default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM 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 R. 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 R. 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, Jirí 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2026-01-27 00:42 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
