Algorithms - ESA 2008

1. Front Matter

   PDF

2. Invited Lectures

   1. Flexible Path Planning Using Corridor Maps

      • Mark Overmars, Ioannis Karamouzas, Roland Geraerts

      Pages 1-12

   2. A Bridging Model for Multi-core Computing

      • Leslie G. Valiant

      Pages 13-28

3. Contributed Papers

   1. Robust Kinetic Convex Hulls in 3D

      • Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Duru Türkoğlu

      Pages 29-40

   2. On Dominance Reporting in 3D

      • Peyman Afshani

      Pages 41-51

   3. Stabbing Convex Polygons with a Segment or a Polygon

      • Pankaj K. Agarwal, Danny Z. Chen, Shashidhara K. Ganjugunte, Ewa Misiołek, Micha Sharir, Kai Tang

      Pages 52-63

   4. An Efficient Algorithm for 2D Euclidean 2-Center with Outliers

      • Pankaj K. Agarwal, Jeff M. Phillips

      Pages 64-75

   5. A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry

      • Spyros Angelopoulos

      Pages 76-87

   6. Cache-Oblivious Red-Blue Line Segment Intersection

      • Lars Arge, Thomas Mølhave, Norbert Zeh

      Pages 88-99

   7. The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains

      • Boris Aronov, Mark de Berg, Shripad Thite

      Pages 100-111

   8. Space-Time Tradeoffs for Proximity Searching in Doubling Spaces

      • Sunil Arya, David M. Mount, Antoine Vigneron, Jian Xia

      Pages 112-123

   9. A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem

      • Maxim A. Babenko, Alexander V. Karzanov

      Pages 124-135

   10. Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs

       • Christian Bachmaier, Wolfgang Brunner

       Pages 136-147

   11. Straight Skeletons of Three-Dimensional Polyhedra

       • Gill Barequet, David Eppstein, Michael T. Goodrich, Amir Vaxman

       Pages 148-160

   12. Randomized Competitive Analysis for Two-Server Problems

       • Wolfgang Bein, Kazuo Iwama, Jun Kawahara

       Pages 161-172

   13. Decompositions and Boundary Coverings of Non-convex Fat Polyhedra

       • Mark de Berg, Chris Gray

       Pages 173-184

   14. Approximating Multi-criteria Max-TSP

       • Markus Bläser, Bodo Manthey, Oliver Putz

       Pages 185-197

   15. An Integer Programming Algorithm for Routing Optimization in IP Networks

       • Andreas Bley

       Pages 198-209

   16. A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling

       • Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller

       Pages 210-221

   17. Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree

       • Paul Bonsma, Frederic Dorn

       Pages 222-233

This book constitutes the refereed proceedings of the 16th Annual European Symposium on Algorithms, ESA 2008, held in Karlsruhe, Germany, in September 2008 in the context of the combined conference ALGO 2008. The 67 revised full papers presented together with 2 invited lectures were carefully reviewed and selected: 51 papers out of 147 submissions for the design and analysis track and 16 out of 53 submissions in the engineering and applications track. The papers address all current subjects in algorithmics reaching from design and analysis issues of algorithms over to real-world applications and engineering of algorithms in various fields. Special focus is given to mathematical programming and operations research, including combinatorial optimization, integer programming, polyhedral combinatorics and network optimization.

• algorithm design
• algorithm theory
• algorithmic mathematics
• algorithmics
• algorithms
• algorithms analysis
• approximation
• combinatorial optimization
• combinatorics
• computational complexity
• distributed algorithms
• dynamic programming
• exact algorithms
• graph algorithms
• graph com
• algorithm analysis and problem complexity

Policies and ethics