default search action
SIAM Journal on Computing, Volume 31
Volume 31, Number 1, 2001
- Jianer Chen, Antonio Miranda:
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling. 1-17 - Ming-Yang Kao, Tak Wah Lam
, Wing-Kin Sung
A Decomposition Theorem for Maximum Weight Bipartite Matchings. 18-26 - Ernst Althaus, Kurt Mehlhorn:
Traveling Salesman-Based Curve Reconstruction in Polynomial Time. 27-66 - Pangfeng Liu, William Aiello, Sandeep N. Bhatt:
Tree Search on an Atomic Model for Message Passing. 67-85 - Stefano Leonardi, Alberto Marchetti-Spaccamela
On-line Randomized Call Control Revisited . 86-112 - Jörg Flum, Martin Grohe:
Fixed-Parameter Tractability, Definability, and Model-Checking. 113-145 - Chandra Chekuri, Rajeev Motwani, B. Natarajan, Clifford Stein:
Approximation Techniques for Average Completion Time Scheduling. 146-166 - Michael Luby, Dana Randall, Alistair Sinclair:
Markov Chain Algorithms for Planar Lattice Structures. 167-192 - Felipe Cucker, Dima Grigoriev:
There are No Sparse NPw-Hard Sets. 193-198 - Antonín Kucera
Randomness and Recursive Enumerability. 199-211 - Vincent Bouchitté, Ioan Todinca:
Treewidth and Minimum Fill-in: Grouping the Minimal Separators. 212-232 - Joan Boyar
The Accommodating Function: A Generalization of the Competitive Ratio. 233-258 - Joe Sawada:
Generating Bracelets in Constant Amortized Time. 259-268 - Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino:
Disjunctions of Horn Theories and Their Cores. 269-288 - Pavol Hell, Ron Shamir
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs. 289-305 - Miklós Csürös, Ming-Yang Kao:
Provably Fast and Accurate Recovery of Evolutionary Trees through Harmonic Greedy Triplets. 306-322 - Jing Chao Chen:
Proportion Extend Sort. 323-330
Volume 31, Number 2, 2001
- Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
Approximating the Throughput of Multiple Machines in Real-Time Scheduling. 331-352 - Rasmus Pagh:
Low Redundancy in Static Dictionaries with Constant Query Time. 353-363 - Monika Rauch Henzinger, Valerie King:
Maintaining Minimum Spanning Forests in Dynamic Graphs. 364-374 - Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg
Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model. 375-397 - Salil P. Vadhan:
The Complexity of Counting in Sparse, Regular, and Planar Graphs. 398-427 - Vojtech Rödl, Andrzej Rucinski
Matchings Meeting Quotas and Their Impact on the Blow-Up Lemma. 428-446 - Gen-Huey Chen, Ming-Yang Kao, Yuh-Dauh Lyuu, Hsing-Kuo Wong:
Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns. 447-459 - Vwani P. Roychowdhury, Farrokh Vatan:
Quantum Formulas: A Lower Bound and Simulation. 460-476 - Joseph Naor, Leonid Zosin:
A 2-Approximation Algorithm for the Directed Multiway Cut Problem. 477-482 - Wolfgang Merkle:
The Global Power of Additional Queries to P-Random Oracles. 483-495 - Ketan Mulmuley, Milind A. Sohoni:
Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. 496-526 - Amotz Bar-Noy, Ari Freund, Joseph Naor:
On-Line Load Balancing in a Hierarchical Server Topology. 527-549 - Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Checking Approximate Computations of Polynomials and Functional Equations. 550-576 - Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel:
The Polygon Exploration Problem. 577-600 - Ashim Garg, Roberto Tamassia:
On the Computational Complexity of Upward and Rectilinear Planarity Testing. 601-625 - Frank Thomson Leighton, Chi-Jen Lu, Satish Rao, Aravind Srinivasan:
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. 626-641 - Hagit Attiya
Adaptive and Efficient Algorithms for Lattice Agreement and Renaming. 642-664
Volume 31, Number 3, 2001
- Moses Charikar, Samir Khuller, Balaji Raghavachari:
Algorithms for Capacitated Vehicle Routing. 665-682 - Conrado Martínez
Optimal Sampling Strategies in Quicksort and Quickselect. 683-705 - Cyril Gavoille, David Peleg:
The Compactness of Interval Routing for Almost All Graphs. 706-721 - Amir M. Ben-Amram, Zvi Galil:
Topological Lower Bounds on Algebraic Random Access Machines. 722-761 - J. Ian Munro, Venkatesh Raman:
Succinct Representation of Balanced Parentheses and Static Trees. 762-776 - Denis Thérien, Thomas Wilke:
Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy. 777-798 - Cristopher Moore
Parallel Quantum Computation and Quantum Codes. 799-815 - Eli Gafni, Michael Mitzenmacher:
Analysis of Timing-Based Mutual Exclusion with Random Times. 816-837 - Joseph Y. Halpern, Yoram Moses, Orli Waarts:
A Characterization of Eventual Byzantine Agreement. 838-865 - Amit Chakrabarti
Evasiveness of Subgraph Containment and Related Properties. 866-875 - Harry Buhrman, Luc Longpré:
Compressibility and Resource Bounded Measure. 876-886 - Harry Buhrman, Lance Fortnow, Sophie Laplante:
Resource-Bounded Kolmogorov Complexity Revisited. 887-905 - Aduri Pavan, Alan L. Selman:
Separation of NP-Completeness Notions. 906-918 - Stavros G. Kolliopoulos, Clifford Stein:
Approximation Algorithms for Single-Source Unsplittable Flow. 919-946 - Michele Boreale
Proof Techniques for Cryptographic Processes. 947-986 - Joachim H. Rieger:
Corrigendum: Proximity in Arrangements of Algebraic Sets. 987
Volume 31, Number 4, 2002
- Yoram Moses, Sergio Rajsbaum
A Layered Analysis of Consensus. 989-1021 - Eduardo Sany Laber, Ruy Luiz Milidiú, Artur Alves Pessoa
On Binary Searching with Nonuniform Costs. 1022-1047 - Paul Beame
The Efficiency of Resolution and Davis--Putnam Procedures. 1048-1075 - Christoph Dürr, Miklos Santha:
A Decision Procedure for Unitary Linear Quantum Cellular Automata. 1076-1089 - Uriel Feige, Robert Krauthgamer
A Polylogarithmic Approximation of the Minimum Bisection. 1090-1118 - Wolfgang Merkle:
Lattice Embeddings for Abstract Bounded Reducibilities. 1119-1155 - Alfons Geser:
Decidability of Termination of Grid String Rewriting Rules. 1156-1168 - Rodney G. Downey, Denis R. Hirschfeldt, André Nies
Randomness, Computability, and Density. 1169-1183 - Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space Complexity in Propositional Calculus. 1184-1211 - Thorsten Theobald:
An Enumerative Geometry Framework for Algorithmic Line Problems in $\mathbb R^3$. 1212-1228 - Leslie G. Valiant:
Quantum Circuits That Can Be Simulated Classically in Polynomial Time. 1229-1254 - Zhi-Zhong Chen, Xin He, Chun-Hsi Huang:
Finding Double Euler Trails of Planar Graphs in Linear Time. 1255-1285 - Hagit Attiya
The Combinatorial Structure of Wait-Free Solvable Tasks. 1286-1313
Volume 31, Number 5, 2002
- Vasek Chvátal, Jean Fonlupt, L. Sun, Abdelhamid Zemirline:
Recognizing Dart-Free Perfect Graphs. 1315-1338 - Yunhong Zhou, Subhash Suri:
Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions. 1339-1357 - Rocco A. Servedio:
Perceptron, Winnow, and PAC Learning. 1358-1369 - Baruch Awerbuch, Yossi Azar
Minimizing the Flow Time Without Migration. 1370-1382 - Moni Naor, Omer Reingold, Alon Rosen:
Pseudorandom Functions and Factoring. 1383-1404 - Ralf Hiptmair, Jörg Ostrowski:
Generators of $H_1(\Gamma_{h}, \mathbbZ)$ for Triangulated Surfaces: Construction and Classification. 1405-1423 - Anna Gál, Adi Rosén:
A Theorem on Sensitivity and Applications in Private Computation. 1424-1437 - Francesco M. Malvestuto, Mauro Mezzini
A Linear Algorithm for Finding the Invariant Edges of an Edge-Weighted Graph. 1438-1455 - Alex Brodsky, Nicholas Pippenger:
Characterizations of 1-Way Quantum Finite Automata. 1456-1478 - Joachim Gudmundsson
Fast Greedy Algorithms for Constructing Sparse Geometric Spanners. 1479-1500 - Adam R. Klivans, Dieter van Melkebeek:
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. 1501-1526 - Martin E. Dyer
On Counting Independent Sets in Sparse Graphs. 1527-1541 - Dieter Spreen:
Safe Weak Minimization Revisited. 1542-1556 - Ilan Newman:
Testing Membership in Languages that Have Small Width Branching Programs. 1557-1570 - Alain J. Mayer, Rafail Ostrovsky, Yoram Ofek, Moti Yung:
Self-Stabilizing Symmetry Breaking in Constant Space. 1571-1595 - Tomás Feder, Rajeev Motwani, Carlos S. Subi:
Approximating the Longest Cycle Problem in Sparse Graphs. 1596-1607 - Eran Halperin:
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs. 1608-1623 - Endre Boros
Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities. 1624-1643
Volume 31, Number 6, 2002
- Alexander Russell
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. 1645-1662 - Venkatesan Guruswami, Johan Håstad
Hardness of Approximate Hypergraph Coloring. 1663-1686 - Hsien-Kuei Hwang
Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions. 1687-1722 - Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
Are Bitvectors Optimal? 1723-1744 - János Pach, Gábor Tardos
On the Boundary Complexity of the Union of Fat Triangles. 1745-1760 - Richard Cole, Ramesh Hariharan:
Approximate String Matching: A Simpler Faster Algorithm. 1761-1782 - Jochen Könemann, R. Ravi:
A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees. 1783-1793 - Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani:
Maintaining Stream Statistics over Sliding Windows. 1794-1813 - Pankaj K. Agarwal, Therese Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, Sue Whitesides:
Curvature-Constrained Shortest Paths in a Convex Polygon. 1814-1851 - Yijie Han, Xiaojun Shen:
Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs. 1852-1878 - Seth Pettie, Vijaya Ramachandran:
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. 1879-1895 - Martin Kutz:
Lower Bounds for Lucas Chains. 1896-1908 - Nader H. Bshouty, Yishay Mansour:
Simple Learning Algorithms for Decision Trees and Multivariate Polynomials. 1909-1925 - Hanno Lefmann, Niels Schmitt
A Deterministic Polynomial-Time Algorithm for Heilbronn's Problem in Three Dimensions. 1926-1947 - Edith Hemaspaandra, Gerd Wechsung:
The Minimization Problem for Boolean Formulas. 1948-1958
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 2025-01-13 00:52 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: