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, Hing-Fung Ting: 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, Alessio Presciutti, Adi Rosén: On-line Randomized Call Control Revisited . 86-112
- 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
- Vincent Bouchitté, Ioan Todinca: Treewidth and Minimum Fill-in: Grouping the Minimal Separators. 212-232
- Joan Boyar, Kim S. Larsen, Morten N. Nielsen: 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, Roded Sharan: 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, Michelle Wagner: 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
- 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, Arie Fouren: 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
- 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
- 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, Subhash Khot, Yaoyun Shi: Evasiveness of Subgraph Containment and Related Properties. 866-875
- Harry Buhrman, Lance Fortnow, Sophie Laplante: Resource-Bounded Kolmogorov Complexity Revisited. 887-905
- Stavros G. Kolliopoulos, Clifford Stein: Approximation Algorithms for Single-Source Unsplittable Flow. 919-946
- Michele Boreale, Rocco De Nicola, Rosario Pugliese: Proof Techniques for Cryptographic Processes. 947-986
- J. H. Rieger: Corrigendum: Proximity in Arrangements of Algebraic Sets. 987
Volume 31, Number 4, 2002
- Eduardo Sany Laber, Ruy Luiz Milidiú, Artur Alves Pessoa: On Binary Searching with Nonuniform Costs. 1022-1047
- Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks: 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
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, Stefano Leonardi, Oded Regev: Minimizing the Flow Time Without Migration. 1370-1382
- Ralf Hiptmair, Jörg Ostrowski: Generators of $H_1(\Gamma_{h}, \mathbbZ)$ for Triangulated Surfaces: Construction and Classification. 1405-1423
- Francesco M. Malvestuto, Mauro Mezzini: A Linear Algorithm for Finding the Invariant Edges of an Edge-Weighted Graph. 1438-1455
- Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan: Fast Greedy Algorithms for Constructing Sparse Geometric Spanners. 1479-1500
- Adam Klivans, Dieter van Melkebeek: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. 1501-1526
- Martin E. Dyer, Alan M. Frieze, Mark Jerrum: 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, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities. 1624-1643
Volume 31, Number 6, 2002
- Alexander Russell, Michael E. Saks, David Zuckerman: Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. 1645-1662
- Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. 1663-1686
- Hsien-Kuei Hwang, Ralph Neininger: 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
- 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 C. 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T203413 by the dblp team