Volume 35, Number 1, 2005
- Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
Some 3CNF Properties Are Hard to Test.
1-21

- Michael Lindenbaum, Hanan Samet, Gísli R. Hjaltason:
A Probabilistic Analysis of Trie-Based Sorting of Large Collections of Line Segments in Spatial Databases.
22-58

- Dieter van Melkebeek, Rahul Santhanam:
Holographic Proofs and Derandmization.
59-90

- Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler:
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.
91-109

- Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel:
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs.
110-119

- Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, David Peleg:
Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds.
120-131

- Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
The Complexity of Approximating the Entropy.
132-150

- Jie Gao, Li Zhang:
Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications.
151-169

- Greg Kuperberg:
A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem.
170-188

- Refael Hassin, Asaf Levin:
A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem.
189-200

- Kazuyuki Amano, Akira Maruoka:
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates.
201-216

- Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan:
Bounds on the Efficiency of Generic Cryptographic Constructions.
217-246

- Guy Kortsarz, Zeev Nutov:
Approximating k-node Connected Subgraphs via Critical Graphs.
247-257

Volume 35, Number 2, 2005
- Petr Hlinený:
A Parametrized Algorithm for Matroid Branch-Width.
259-277

- Susanne Albers, Markus Schmidt:
On the Performance of Greedy Algorithms in Packet Buffering.
278-304

- Costas Busch, Srikanta Tirthapura:
Analysis of Link Reversal Routing Algorithms.
305-326

- Ketan Dalal, Luc Devroye, Ebrahim Malalla, Erin McLeish:
Two-Way Chaining with Reassignment.
327-340

- Michael A. Bender, Erik D. Demaine, Martin Farach-Colton:
Cache-Oblivious B-Trees.
341-358

- Gyung-Ok Lee, Kwang-Moo Choe:
A Powerful LL(k) Covering Transformation.
359-377

- Roberto Grossi, Jeffrey Scott Vitter:
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching.
378-407

- Joel Friedman, Andreas Goerdt, Michael Krivelevich:
Recognizing More Unsatisfiable Random k-SAT Instances Efficiently.
408-430

- Leah Epstein, Rob van Stee:
Optimal Online Algorithms for Multidimensional Packing Problems.
431-448

- April Rasala Lehman, Gordon T. Wilfong:
http: //epubs.siam.org/SICOMP/volume-35/art_43425.html.
449-485

- Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
Strong Spatial Mixing with Fewer Colors for Lattice Graphs.
486-517

Volume 35, Number 3, 2005
- Klaus Jansen, Lorant Porkolab:
General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time.
519-530

- Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia:
Optimal Covering Tours with Turn Costs.
531-566

- Darin Goldstein, Kojiro Kobayashi:
On the Complexity of Network Synchronization.
567-589

- Ernst-Erich Doberkat:
Stochastic Relations: Congruences, Bisimulations and the Hennessy--Milner Theorem.
590-626

- Bernard Chazelle, Ding Liu, Avner Magen:
Sublinear Geometric Algorithms.
627-646

- Bjørn Kjos-Hanssen, André Nies, Frank Stephan:
Lowness for the Class of Schnorr Random Reals.
647-657

- Minming Li, F. Frances Yao:
An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules.
658-671

- Michael Elkin, Guy Kortsarz:
A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem.
672-689

- Dirk L. Vertigan:
The Computational Complexity of Tutte Invariants for Planar Graphs.
690-712

- Chandra Chekuri, Sanjeev Khanna:
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem.
713-728

- Weiping Shi, Chen Su:
The Rectilinear Steiner Arborescence Problem Is NP-Complete.
729-740

- Meghanad D. Wagh, Osman Guzide:
Mapping Cycles and Trees on Wrap-Around Butterfly Graphs.
741-765

- Hung Quang Ngo:
WDM Switching Networks, Rearrangeable and Nonblocking [w, f]-connectors.
766-785

Volume 35, Number 4, 2006
Volume 35, Number 5, 2006
- Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat:
Function Matching.
1007-1022

- Sean Curran, Orlando Lee, Xingxing Yu:
Finding Four Independent Trees .
1023-1058

- Holger Petersen, John Michael Robson:
Efficient Simulations by Queue Machines.
1059-1069

- Julia Kempe, Alexei Kitaev, Oded Regev:
The Complexity of the Local Hamiltonian Problem.
1070-1097

- Jesper Jansson, Nguyen Bao Nguyen, Wing-Kin Sung:
Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network.
1098-1121

- Karl-Heinz Niggl, Henning Wunderlich:
Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs.
1122-1147

- Sariel Har-Peled, Manor Mendel:
Fast Construction of Nets in Low-Dimensional Metrics and Their Applications.
1148-1184

- Omer Reingold, Ronen Shaltiel, Avi Wigderson:
Extracting Randomness via Repeated Condensing.
1185-1209

- Markus Lohrey:
Word Problems and Membership Problems on Compressed Words.
1210-1240

- Maurice Queyranne, Andreas S. Schulz:
Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems.
1241-1253

- Moni Naor, Benny Pinkas:
Oblivious Polynomial Evaluation.
1254-1281

Volume 35, Number 6, 2006
- Klaus Weihrauch, Ning Zhong:
An Algorithm for Computing Fundamental Solutions.
1283-1294

- Serge Abiteboul, Stephen Alstrup, Haim Kaplan, Tova Milo, Theis Rauhe:
Compact Labeling Scheme for Ancestor Queries.
1295-1309

- Christoph Dürr, Mark Heiligman, Peter Høyer, Mehdi Mhalla:
Quantum Query Complexity of Some Graph Problems.
1310-1328

- Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
The Approximability of Three-valued MAX CSP.
1329-1349

- Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking:
Balanced Allocations: The Heavily Loaded Case.
1350-1385

- Floris Geerts, Bart Kuijpers, Jan Van den Bussche:
Linearization and Completeness Results for Terminating Transitive Closure Queries on Spatial Databases.
1386-1439

- Hua-Huai Chern, Hsien-Kuei Hwang:
Partial Match Queries in Random k-d Trees.
1440-1466

- Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
Power from Random Strings.
1467-1493

- Christian Worm Mortensen:
Fully Dynamic Orthogonal Range Reporting on RAM.
1494-1525

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