Algorithmica, Volume 42, 2005

Volume 42, Number 1, March 2005

• Prosenjit Bose, Pat Morin:
  Guest Editors' Foreword. 1-2
  
• John Iacono:
  Key-Independent Optimality. 3-10
  
• Luc Devroye:
  Universal Asymptotics for Random Tries and PATRICIA Trees. 11-29
  
• Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich:
  Biased Skip Lists. 31-48
  
• John Iacono, Stefan Langerman:
  Queaps. 49-56
  
• Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, Emily Rocke:
  Characterizing History Independent Data Structures. 57-74
  
• Sumanta Guha, Son Dinh Tran:
  Reconstructing Curves without Delaunay Computation. 75-94
  
• Hiroshi Fujiwara, Kazuo Iwama:
  Average-Case Competitive Analyses for Ski-Rental Problems. 95-107
  

Volume 42, Number 2, April 2005

• Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky:
  Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. 109-120
  
• Markus Bläser, Bodo Manthey:
  Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One. 121-139
  
• Kenichiro Ohta, Kunihiko Sadakane, Akiyoshi Shioura, Takeshi Tokuyama:
  A Fast, Accurate, and Simple Method for Pricing European-Asian and Saving-Asian Options. 141-158
  
• Seok-Hee Hong, Peter Eades:
  Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs. 159-197
  

Volume 42, Number 3-4, June 2005

• Rolf H. Möhring, Rajeev Raman:
  Preface. 199-201
  
• Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, Yusu Wang:
  Near-Linear Time Approximation Algorithms for Curve Simplification. 203-219
  
• Pankaj K. Agarwal, Cecilia Magdalena Procopiuc, Kasturi R. Varadarajan:
  Approximation Algorithms for a k-Line Center. 221-230
  
• Georg Baier, Ekkehard Köhler, Martin Skutella:
  The k-Splittable Flow Problem. 231-248
  
• Prosenjit Bose, Joachim Gudmundsson, Michiel H. M. Smid:
  Constructing Plane Spanners of Bounded Degree and Low Weight. 249-264
  
• Danny Z. Chen, Xiaobo Sharon Hu, Shuang Luan, Xiaodong Wu, Cedric X. Yu:
  Optimal Terrain Construction Problems and Applications in Intensity-Modulated Radiation Therapy. 265-288
  
• Kirk Pruhs, Patchrawat Uthaisombut:
  A Comparison of Multicast Pull Models. 289-307
  
• Hadas Shachnai, Tami Tamir, Gerhard J. Woeginger:
  Minimizing Makespan and Preemption Costs on a System of Uniform Machines. 309-334