Algorithms and Computation

1. Front Matter

   PDF

2. Invited Talk I

   1. Algorithm Engineering for Route Planning – An Update –

      • Dorothea Wagner

      Pages 1-5

3. Invited Talk II

   1. Semidefinite Programming and Approximation Algorithms: A Survey

      • Sanjeev Arora

      Pages 6-9

4. Approximation Algorithms I

   1. The School Bus Problem on Trees

      • Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità

      Pages 10-19

   2. Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph

      • M. Reza Khani, Mohammad R. Salavatipour

      Pages 20-29

   3. Improved Approximation Algorithms for Routing Shop Scheduling

      • Wei Yu, Guochuan Zhang

      Pages 30-39

   4. Contraction-Based Steiner Tree Approximations in Practice

      • Markus Chimani, Matthias Woste

      Pages 40-49

5. Computational Geometry I

   1. Covering and Piercing Disks with Two Centers

      • Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin, Antoine Vigneron

      Pages 50-59

   2. Generating Realistic Roofs over a Rectilinear Polygon

      • Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin, Antoine Vigneron

      Pages 60-69

   3. Computing the Visibility Polygon Using Few Variables

      • Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira

      Pages 70-79

   4. Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius

      • Matias Korman

      Pages 80-89

6. Graph Algorithms

   1. Hamiltonian Paths in the Square of a Tree

      • Jakub Radoszewski, Wojciech Rytter

      Pages 90-99

   2. Dominating Induced Matchings for P ₇-free Graphs in Linear Time

      • Andreas Brandstädt, Raffaele Mosca

      Pages 100-109

   3. Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths

      • Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van ’t Hof, Marcin Kamiński, Daniël Paulusma

      Pages 110-119

   4. Recognizing Polar Planar Graphs Using New Results for Monopolarity

      • Van Bang Le, Ragnar Nevries

      Pages 120-129

   5. Robustness of Minimum Cost Arborescences

      • Naoyuki Kamiyama

      Pages 130-139

7. Data Structures I

   1. Path Queries in Weighted Trees

      • Meng He, J. Ian Munro, Gelin Zhou

      Pages 140-149

   2. Dynamic Range Majority Data Structures

      • Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson

      Pages 150-159

   3. Dynamic Range Selection in Linear Space

      • Meng He, J. Ian Munro, Patrick K. Nicholson

      Pages 160-169

   4. A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time

      • Yakov Nekrich

      Pages 170-179

This book constitutes the refereed proceedings of the 22nd International Symposium on Algorithms and Computation, ISAAC 2011, held in Yokohama, Japan in December 2011. The 76 revised full papers presented together with two invited talks were carefully reviewed and selected from 187 submissions for inclusion in the book. This volume contains topics such as approximation algorithms; computational geometry; computational biology; computational complexity; data structures; distributed systems; graph algorithms; graph drawing and information visualization; optimization; online and streaming algorithms; parallel and external memory algorithms; parameterized algorithms; game theory and internet algorithms; randomized algorithms; and string algorithms.

• distributed algorithm
• mesh data structures
• optimization
• space complexity
• vehicle routing
• algorithm analysis and problem complexity
• data structures

• Chuo University, Tokyo, Japan

  Takao Asano

• Gunma University, Kiryu-Shi, Japan

  Shin-ichi Nakano

• Japan Advanced Institute of Science and Technology, Nomi, Japan

  Yoshio Okamoto

• Tokyo Institute of Technology, Tokyo, Japan

  Osamu Watanabe

Policies and ethics