Algorithmica, Volume 43, 2005

Volume 43, Number 1-2, August 2005

Lisa Zhang:
Guest Editor's Introduction. 1-3
Ashish Goel, Deborah Estrin:
Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk. 5-15
Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph Naor, Danny Raz:
Building Edge-Failure Resilient Networks. 17-41
Thomas Erlebach, Stamatis Stefanakos:
Wavelength Conversion in All-Optical Networks with Shortest-Path Routing. 43-61
Alexander Kesselman, Yishay Mansour, Rob van Stee:
Improved Competitive Guarantees for QoS Buffering. 63-80
Yossi Azar, Yossi Richter:
Management of Multi-Queue Switches in QoS Networks. 81-96
Alexander Kesselman, Yishay Mansour:
Adaptive AIMD Congestion Control. 97-111
Jessica H. Fong, Anna C. Gilbert, Sampath Kannan, Martin J. Strauss:
Better Alternatives to OSPF Routing. 113-131
Jay Sethuraman, Chung-Piaw Teo:
Effective Routing and Scheduling in Adversarial Queueing Networks. 133-146

Zhi-Zhong Chen, Mitsuharu Kouno:
A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs. 147-177
Nadav Efraty, Gad M. Landau:
Sparse Normalized Local Alignment. 179-194
Ho Kyung Kim, Leonidas J. Guibas, Sung Yong Shin:
Efficient Collision Detection among Moving Spheres with Unknown Trajectories. 195-210
Olgica Milenkovic, Kevin J. Compton:
Average Case Analysis of Gosper's Algorithm for a Class of Urn Model Inputs. 211-244

Jianer Chen, Iyad A. Kanj, Ge Xia:
Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems. 245-273
David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao:
Representing Trees of Higher Degree. 275-292
Jesper Jansson, Joseph H.-K. Ng, Kunihiko Sadakane, Wing-Kin Sung:
Rooted Maximum Agreement Supertrees. 293-307
Mahesh Kallahalla, Peter J. Varman:
Optimal Read-Once Parallel Disk Scheduling. 309-343