SIAM Journal on Computing, Volume 29

Volume 29, Number 1, September 1999

• Uriel Feige, Dror Lapidot, Adi Shamir:
  Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions. 1-28
  
• Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman:
  Tight Analyses of Two Local Load Balancing Algorithms. 29-64
  
• Xin He, Zhi-Zhong Chen:
  An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications. 65-80
  
• Eberhard Bertsch, Mark-Jan Nederhof:
  Regular Closure of Deterministic Languages. 81-102
  
• Maria Luisa Bonet, Cynthia A. Phillips, Tandy Warnow, Shibu Yooseph:
  Constructing Evolutionary Trees in the Presence of Polymorphic Characters. 103-131
  
• E. Allen Emerson, Charanjit S. Jutla:
  The Complexity of Tree Automata and Logics of Programs. 132-158
  
• Naveen Garg, Huzur Saran, Vijay V. Vazirani:
  Finding Separator Cuts in Planar Graphs within Twice the Optimal. 159-179
  
• Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal:
  Balanced Allocations. 180-200
  
• Claudia Bertram-Kretzberg, Hanno Lefmann:
  The Algorithmic Aspects of Uncrowded Hypergraphs. 201-230
  
• Jerzy Marcinkowski:
  Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs. 231-257
  
• Frank Thomson Leighton, Yuan Ma:
  Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults. 258-273
  
• Tibor Szkaliczki:
  Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is NP-Complete. 274-287
  
• Weimin Chen, Volker Turau:
  On Regular Tree Embeddings. 288-301
  
• Josef M. Breutzmann, Jack H. Lutz:
  Equivalence of Measures of Complexity Classes. 302-326
  
• Shoshana Anily, Michel Gendreau, Gilbert Laporte:
  The Swapping Problem on a Line. 327-335
  
• Howard J. Karloff:
  How Good is the Goemans-Williamson MAX CUT Algorithm? 336-350
  

Volume 29, Number 2, October-December 1999

• Benny Chor, Lee-Bath Nelson:
  Solvability in Asynchronous Environments II: Finite Interactive Tasks. 351-377
  
• Elaine M. Eschen, Ryan Hayward, Jeremy Spinrad, R. Sritharan:
  Weakly Triangulated Comparability Graphs. 378-386
  
• Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum:
  On Approximately Counting Colorings of Small Degree Graphs. 387-400
  
• Stephen J. Bellantoni, Karl-Heinz Niggl:
  Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited. 401-415
  
• Michael T. Goodrich:
  Communication-Efficient Parallel Sorting. 416-432
  
• J. H. Rieger:
  Proximity in Arrangements of Algebraic Sets. 433-458
  
• Susanne Albers:
  Better Bounds for Online Scheduling. 459-473
  
• Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu:
  Tight Bounds for On-Line Tree Embeddings. 474-491
  
• David R. Karger:
  A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem. 492-514
  
• Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven Skiena, Tae-Cheon Yang:
  On the Maximum Scatter Traveling Salesperson Problem. 515-544
  
• Rodney G. Downey, Michael R. Fellows, Alexander Vardy, Geoff Whittle:
  The Parametrized Complexity of Some Fundamental Problems in Coding Theory. 545-570
  
• Juha Kärkkäinen, Esko Ukkonen:
  Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time. 571-589
  
• Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi:
  Kolmogorov Random Graphs and the Incompressibility Method. 590-599
  
• Steven C. Bruell, Sukumar Ghosh, Mehmet Hakan Karaata, Sriram V. Pemmaraju:
  Self-Stabilizing Algorithms for Finding Centers and Medians of Trees. 600-614
  
• Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang:
  Automatic Methods for Hiding Latency in Parallel and Distributed Computation. 615-647
  
• Aravind Srinivasan:
  Improved Approximation Guarantees for Packing and Covering Integer Programs. 648-670
  
• Frank Ruskey, Joe Sawada:
  An Efficient Algorithm for Generating Necklaces with Fixed Density. 671-684
  
• Zhivko Prodanov Nedev:
  Finding an Even Simple Path in a Directed Planar Graph. 685-695
  

Volume 29, Number 3, December 1999

• Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber:
  The Angular-Metric Traveling Salesman Problem. 697-711
  
• B. Natarajan:
  On Learning Functions from Noise-Free and Noisy Samples via Occam's Razor. 712-727
  
• Mark Levene, George Loizou:
  Navigation in Hypertext Is Easy Only Sometimes. 728-760
  
• Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang:
  A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees. 761-778
  
• Paolo Boldi, Sebastiano Vigna:
  Complexity of Deciding Sense of Direction. 779-789
  
• Amos Fiat, Moni Naor:
  Rigorous Time/Space Trade-offs for Inverting Functions. 790-803
  
• Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg:
  Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks. 804-833
  
• Leslie Ann Goldberg, Mark Jerrum:
  Randomly Sampling Molecules. 834-853
  
• Scott E. Decatur, Oded Goldreich, Dana Ron:
  Computational Sample Complexity. 854-879
  
• Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
  A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. 880-892
  
• S. Rao Kosaraju, Giovanni Manzini:
  Compression of Low Entropy Strings with Lempel-Ziv Algorithms. 893-911
  
• Pankaj K. Agarwal, Alon Efrat, Micha Sharir:
  Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications. 912-953
  
• Z. Sweedyk:
  A 2½-Approximation Algorithm for Shortest Superstring. 954-986
  
• Ioan I. Macarie:
  On the Structure of Logspace Probabilistic Complexity Classes. 987-1007
  
• Flávio Keidi Miyazawa, Yoshiko Wakabayashi:
  Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem. 1008-1029
  

Volume 29, Number 3, January 2000

• Dan E. Willard:
  Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree. 1030-1049
  

Volume 29, Number 4, 2000

• Tracy Kimbrel, Anna R. Karlin:
  Near-Optimal Parallel Prefetching and Caching. 1051-1082
  
• Leszek Pacholski, Wieslaw Szwast, Lidia Tendera:
  Complexity Results for First-Order Two-Variable Logic with Counting. 1083-1117
  
• Klaus Reinhardt, Eric Allender:
  Making Nondeterminism Unambiguous. 1118-1131
  
• Oded Goldreich, Shmuel Safra:
  A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. 1132-1154
  
• Sridhar Rajagopalan, Leonard J. Schulman:
  Verification of Identities. 1155-1163
  
• Susanne Albers, Monika Rauch Henzinger:
  Exploring Unknown Environments. 1164-1188
  
• Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky:
  Reducibility and Completeness in Private Computations. 1189-1208
  
• Vince Grolmusz, Gábor Tardos:
  Lower Bounds for (MOD_p-MOD_m) Circuits. 1209-1222
  
• Danny Z. Chen, Kevin S. Klenk, Hung-Yi Tu:
  Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane. 1223-1246
  
• Zhi-Zhong Chen, Ming-Yang Kao:
  Reducing Randomness via Irrational Numbers. 1247-1256
  
• Wei-Liang Lin, Amir H. Farrahi, Majid Sarrafzadeh:
  On the Power of Logic Resynthesis. 1257-1289
  
• Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter:
  Application-Controlled Paging for a Shared Cache. 1290-1303
  
• Ravi B. Boppana, Babu O. Narayanan:
  Perfect-Information Leader Election with Optimal Resilience. 1304-1320
  
• Alok Aggarwal, Jon M. Kleinberg, David P. Williamson:
  Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. 1321-1333
  
• Scott A. Mitchell, Stephen A. Vavasis:
  Quality Mesh Generation in Higher Dimensions. 1334-1370
  
• Edward P. F. Chan, Ron van der Meyden:
  Containment and Optimization of Object-Preserving Conjunctive Queries. 1371-1400
  

Volume 29, Number 5, 2000

• Jean-Daniel Boissonnat, Franco P. Preparata:
  Robust Plane Sweep for Intersecting Segments. 1401-1421
  
• Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter:
  Binary Space Partitions for Fat Rectangles. 1422-1448
  
• Michael E. Saks, Fotios Zaharoglou:
  Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. 1449-1483
  
• Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross:
  An Optimal Algorithm for Monte Carlo Estimation. 1484-1496
  
• Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet:
  Separating Complexity Classes Using Autoreducibility. 1497-1520
  
• Johannes A. La Poutré:
  Maintenance of 2- and 3-Edge-Connected Components of Graphs II. 1521-1549
  
• Millist W. Vincent, Mark Levene:
  Restructuring Partitioned Normal Form Relations without Information Loss. 1550-1567
  
• Ming-Yang Kao, Jie Wang:
  Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors. 1568-1576
  
• Jürgen Sellen, Joonsoo Choi, Chee-Keng Yap:
  Precision-Sensitive Euclidean Shortest Path in 3-Space. 1577-1595
  
• Oren Etzioni, Steve Hanks, Tao Jiang, Omid Madani:
  Optimal Information Gathering on the Internet with Time and Cost Constraints. 1596-1620
  
• Ladislav Stacho, Imrich Vrto:
  Virtual Path Layouts in ATM Networks. 1621-1629
  
• Funda Ergün, Ravi Kumar, D. Sivakumar:
  Self-Testing without the Generator Bottleneck. 1630-1651
  
• Michael Benedikt, Leonid Libkin:
  Safe Constraint Queries. 1652-1682
  
• Sanjeev Khanna, Vincenzo Liberatore:
  On Broadcast Disk Paging. 1683-1702
  
• Artur Czumaj, Friedhelm Meyer auf der Heide, Volker Stemann:
  Contention Resolution in Hashing Based Shared Memory Simulations. 1703-1739
  
• Dorit Dor, Shay Halperin, Uri Zwick:
  All-Pairs Almost Shortest Paths. 1740-1759
  

Volume 29, Number 6, 2000

• Monika Rauch Henzinger:
  Improved Data Structures for Fully Dynamic Biconnectivity. 1761-1815
  
• Håkan Lennerstad, Lars Lundberg:
  Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems. 1816-1838
  
• Joachim von zur Gathen, Igor Shparlinski:
  The CREW PRAM Complexity of Modular Inversion. 1839-1857
  
• Sanjiv Kapoor:
  Dynamic Maintenance of Maxima of 2-d Point Sets. 1858-1877
  
• Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein:
  The Complexity of the A B C Problem. 1878-1888
  
• Dahlia Malkhi, Michael K. Reiter, Avishai Wool:
  The Load and Availability of Byzantine Quorum Systems. 1889-1906
  
• Avrim Blum, Prasad Chalasani:
  An Online Algorithm for Improving Performance in Navigation. 1907-1938
  
• Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
  On Interpolation and Automatization for Frege Systems. 1939-1967
  
• Jeff Erickson:
  Space-Time Tradeoffs for Emptiness Queries. 1968-1996
  
• Micah Adler, John W. Byers, Richard M. Karp:
  Parallel Sorting with Limited Bandwidth. 1997-2015
  
• Sariel Har-Peled:
  Constructing Planar Cuttings in Theory and Practice. 2016-2039
  
• Marcos Kawazoe Aguilera, Wei Chen, Sam Toueg:
  On Quiescent Reliable Communication. 2040-2073
  
• Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
  Gadgets, Approximation, and Linear Programming. 2074-2097
  

Last update Sat May 18 20:52:33 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page