Algorithmica, Volume 55, 2009

Volume 55, Number 1, September 2009

• Jianer Chen, Yang Liu, Songjian Lu:
  An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem. 1-13
  
• Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt:
  A Separation Bound for Real Algebraic Expressions. 14-28
  
• Marek Karpinski, Yakov Nekrich:
  A Fast Algorithm for Adaptive Prefix Coding. 29-41
  
• Benjamin E. Birnbaum, Kenneth J. Goldman:
  An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs. 42-59
  
• Costas S. Iliopoulos, M. Sohel Rahman:
  Indexing Factors with Gaps. 60-70
  
• Stanislav Angelov, Sanjeev Khanna, Keshav Kunal:
  The Network as a Storage Device: Dynamic Routing with Bounded Buffers. 71-94
  
• Rafael C. Carrasco, Jan Daciuk, Mikel L. Forcada:
  Incremental Construction of Minimal Tree Automata. 95-110
  
• Chandra Chekuri, Luca Trevisan:
  Foreword. 111-112
  
• Eyal Kaplan, Moni Naor, Omer Reingold:
  Derandomized Constructions of k-Wise (Almost) Independent Permutations. 113-133
  
• Christopher Umans:
  Reconstructive Dispersers and Hitting Set Generators. 134-156
  
• Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar:
  What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. 157-189
  
• Uriel Feige, Kunal Talwar:
  Approximating the Bandwidth of Caterpillars. 190-204
  
• V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
  Scheduling on Unrelated Machines under Tree-Like Precedence Constraints. 205-226
  
• Julián Mestre:
  A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. 227-239
  
• Jan Remy, Angelika Steger:
  Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems. 240-267
  

Volume 55, Number 2, October 2009

• Lars Arge, Emo Welzl:
  Foreword. 269-270
  
• Jakub Pawlewicz, Mihai Patrascu:
  Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons. 271-282
  
• Haim Kaplan, Natan Rubin, Micha Sharir:
  Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra. 283-310
  
• Julian Lorenz, Konstantinos Panagiotou, Angelika Steger:
  Optimal Algorithms for k-Search with Application in Option Pricing. 311-328
  
• Peter Hachenberger:
  Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces. 329-345
  
• Giorgio Ausiello, Camil Demetrescu, Paolo Giulio Franciosa, Giuseppe F. Italiano, Andrea Ribichini:
  Graph Spanners in the Streaming Model: An Experimental Study. 346-374
  
• Arie M. C. A. Koster, Adrian Zymolka, Manuel Kutschka:
  Algorithms to Separate {0, \frac12}\{0, \frac{1}{2}\} -Chvátal-Gomory Cuts. 375-391
  

Volume 55, Number 3, November 2009

• Frédéric Magniez, Ashwin Nayak:
  Foreword from the Guest Editors. 393-394
  
• Dorit Aharonov, Vaughan Jones, Zeph Landau:
  A Polynomial Quantum Algorithm for Approximating the Jones Polynomial. 395-421
  
• Andris Ambainis, Robert Spalek, Ronald de Wolf:
  A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. 422-461
  
• Ran Raz:
  Quantum Information and the PCP Theorem. 462-489
  
• Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen:
  Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem. 490-516
  
• Ben Reichardt:
  Error-Detection-Based Quantum Fault-Tolerance Threshold. 517-556
  
• Miklos Santha, Mario Szegedy:
  Quantum and Classical Query Complexities of Local Search Are Polynomially Related. 557-575
  
• Xiaoming Sun, Andrew Chi-Chih Yao:
  On the Quantum Query Complexity of Local Search in Two and Three Dimensions. 576-600
  

Volume 55, Number 4, December 2009

• Binay K. Bhattacharya, Qiaosheng Shi, Arie Tamir:
  Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees. 601-618
  
• Peter Damaschke, Phuong Hoai Ha, Philippas Tsigas:
  Online Search with Time-Varying Price Bounds. 619-642
  
• Leah Epstein, Magnús M. Halldórsson, Asaf Levin, Hadas Shachnai:
  Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs. 643-665
  
• Prosenjit Bose, Pat Morin, Michiel H. M. Smid, Stefanie Wuhrer:
  Clamshell Casting. 666-702
  
• Rebecca Robinson, Graham Farr:
  Structure and Recognition of Graphs with No 6-wheel Subdivision. 703-728
  
• George Christodoulou, Elias Koutsoupias, Angelina Vidali:
  A Lower Bound for Scheduling Mechanisms. 729-740