Includes bibliographical references and author index.

Annotation 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.

Intro; Title page; Preface; Organization; Table of Contents; Invited Talk I; Algorithm Engineering for Route Planning- An Update -; References; Invited Talk II; Semidefinite Programming and Approximation Algorithms: A Survey; References; Approximation Algorithms I; The School Bus Problem on Trees; Introduction; Our Results; Related Work; Preliminaries; A 4-Approximation to the SBP on Trees; A 12.5-Approximation to the Uncapacitated SBP-R on Trees; References; Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k, 2)-Subgraph; Introduction

Shallow-Light Steiner TreesAn O(logn)-Approximation for the (k, 2)-Subgraph Problem; References; Improved Approximation Algorithms for Routing Shop Scheduling; Introduction; Previous Work; Our Results and Techniques; Preliminaries; Routing Open Shop; Routing Flow Shop; References; Contraction-Based Steiner Tree Approximations in Practice; Introduction; History; Contraction Framework; Algorithm Engineering; Experiments; Conclusions and Thoughts; References; Computational Geometry I; Covering and Piercing Disks with Two Centers; Introduction; Intersecting Disks with Two Centers

Decision AlgorithmOptimization Algorithm; Covering Disks with Two Centers; The General Case; The Restricted Case; References; Generating Realistic Roofs over a Rectilinear Polygon; Introduction; Preliminaries; Properties of Realistic Roofs; Local Properties of Valleys and Ridges; Global Structure of Realistic Roofs; Enumerating Realistic Roofs and Computing Optimal Roofs; References; Computing the Visibility Polygon Using Few Variables; Introduction; Preliminaries; An O(n) Algorithm Using O(1) Variables; An O(n logr) Algorithm Using O(logr) Variables; Closing Remarks; References

Minimizing Interference in Ad-Hoc Networks with Bounded Communication RadiusIntroduction; Definitions and Results; Layered Nearest Neighbor Algorithm; Bounded Radius Network; Conclusion; References; Graph Algorithms; Hamiltonian Paths in the Square of a Tree; Introduction; Caterpillars and Horsetails; 2H-Paths in (u, v)-Horsetails; Efficient Algorithm for Horstail Queries; References; Dominating Induced Matchings for P7-free Graphs in Linear Time; Introduction and Basic Notions; Simple Properties of Graphs with Dominating Induced Matching

Structure of P7-free Graphs with Dominating Induced MatchingDistance Levels with Respect to an M-Edge in a P3; Edges in and between Ti and Tj, i =j; The Algorithm for the General P7-free Case; Conclusion; References; Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths; Introduction; Preliminaries; Set-Restricted Disjoint Paths; Contractions and Induced Minors in Chordal Graphs; Concluding Remarks; References; Recognizing Polar Planar Graphs Using New Results for Monopolarity; Introduction; Hardness Results; A 2-SAT Approach and a Superclass of Chair-Free Graphs