default search action
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 J. 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 P. Spinrad, R. Sritharan:
Weakly Triangulated Comparability Graphs. 378-386 - Russ Bubley
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 - Joachim 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
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
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 - Balas K. 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
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
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
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
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
Lower Bounds for (MODp-MODm) 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
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
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 E. 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
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
On Quiescent Reliable Communication. 2040-2073 - Luca Trevisan
Gadgets, Approximation, and Linear Programming. 2074-2097
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 2024-11-15 19:21 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: