Algorithms and Computation

This book constitutes the refereed proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, held in Honolulu, Hawaii, USA in December 2009. The 120 revised full papers presented were carefully reviewed and selected from 279 submissions for inclusion in the book. This volume contains topics such as algorithms and data structures, approximation algorithms, combinatorial optimization, computational biology, computational complexity, computational geometry, cryptography, experimental algorithm methodologies, graph drawing and graph algorithms, internet algorithms, online algorithms, parallel and distributed algorithms, quantum computing and randomized algorithms.

Inhalt
Bubblesort and Juggling Sequences.- A Proof of the Molecular Conjecture.- Exact Algorithms for Dominating Clique Problems.- Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming.- Exact Algorithms for the Bottleneck Steiner Tree Problem.- Exact Algorithms for Set Multicover and Multiset Multicover Problems.- Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm.- Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems.- On Protein Structure Alignment under Distance Constraint.- A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability.- Max-Coloring Paths: Tight Bounds and Extensions.- Fréchet Distance Problems in Weighted Regions.- The Complexity of Solving Stochastic Games on Graphs.- Computational Complexity of Cast Puzzles.- New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body.- Reconstructing Numbers from Pairwise Function Values.- Hilbert's Thirteenth Problem and Circuit Complexity.- Interval Stabbing Problems in Small Integer Ranges.- Online Sorted Range Reporting.- Data Structures for Approximate Orthogonal Range Counting.- Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time.- Untangled Monotonic Chains and Adaptive Range Search.- Geodesic Spanners on Polyhedral Surfaces.- Approximating Points by a Piecewise Linear Function: I.- Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers.- Computing the Map of Geometric Minimal Cuts.- On the Camera Placement Problem.- Graph Orientations with Set Connectivity Requirements.- A Linear Vertex Kernel for Maximum Internal Spanning Tree.- Geometric Minimum Diameter Minimum Cost Spanning Tree Problem.- On Shortest Disjoint Paths in PlanarGraphs.- An Optimal Labeling for Node Connectivity.- SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks.- 1-Bounded Space Algorithms for 2-Dimensional Bin Packing.- On the Advice Complexity of Online Problems.- Online Knapsack Problems with Limited Cuts.- Online Paging for Flash Memory Devices.- Shifting Strategy for Geometric Graphs without Geometry.- Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics.- Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time.- Minimum Covering with Travel Cost.- Route-Enabling Graph Orientation Problems.- Complexity of Approximating the Vertex Centroid of a Polyhedron.- Popular Matchings with Variable Job Capacities.- On the Tightness of the Buhrman-Cleve-Wigderson Simulation.- Bounds on Contention Management Algorithms.- Algorithmic Folding Complexity.- Min-Energy Scheduling for Aligned Jobs in Accelerate Model.- Posi-modular Systems with Modulotone Requirements under Permutation Constraints.- Generalized Reduction to Compute Toric Ideals.- Linear and Sublinear Time Algorithms for Basis of Abelian Groups.- Good Programming in Transactional Memory.- Induced Packing of Odd Cycles in a Planar Graph.- On the Infinitesimal Rigidity of Bar-and-Slider Frameworks.- Exploration of Periodically Varying Graphs.- Parameterized Complexity of Arc-Weighted Directed Steiner Problems.- Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries.- Minimum Cycle Bases of Weighted Outerplanar Graphs.- Bandwidth on AT-Free Graphs.- Editing Graphs into Disjoint Unions of Dense Clusters.- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs.- Parameterizing Cut Sets in a Graph by the Number of Their Components.- Inapproximability of Maximal Strip Recovery.- The Complexity of Perfect Matching Problems on Dense Hypergraphs.- On Lower Bounds for Constant Width Arithmetic Circuits.- Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.- The Identity Correspondence Problem and Its Applications.- Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs.- An Improved Approximation Algorithm for the Traveling Tournament Problem.- The Fault-Tolerant Facility Allocation Problem.- Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks.- Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms.- The Directed Hausdorff Distance between Imprecise Point Sets.- Computing Multidimensional Persistence.- Locating an Obnoxious Line among Planar Objects.- Finding Fullerene Patches in Polynomial Time.- Convex Drawings of Internally Triconnected Plane Graphs on O(n 2) Grids.- A Self-stabilizing and Local Delaunay Graph Construction.- Succinct Greedy Geometric Routing in the Euclidean Plane.- Electric Routing and Concurrent Flow Cutting.- A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths.- Strong Robustness of Randomized Rumor Spreading Protocols.- Data Structures for Range Median Queries.- Deletion without Rebalancing in Multiway Search Trees.- Counting in the Presence of Memory Faults.- A Simple, Fast, and Compact Static Dictionary.- Reconstructing Polygons from Scanner Data.- Computing Large Matchings in Planar Graphs with Fixed Minimum Degree.- Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs.- Covering a Graph with a Constrained Forest (Extended Abstract).- Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs.- Upward Star-Shaped Polyhedral Graphs.- Conditional Hardness of Approximating Satisfiable Max 3CSP-q.- The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract).- Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement.- Step-Assembly with a Constant Number of Tile Types.- Lower Bounds on Fast Searching.- Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity.- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1?+?? ) Time.- PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k.- Optimal Randomized Algorithm for the Density Selection Problem.- New Results on Simple Stochastic Games.- Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.- Succinct Index for Dynamic Dictionary Matching.- Range Non-overlapping Indexing.- Querying Two Boundary Points for Shortest Paths in a Polygonal Domain.- Pattern Matching for 321-Avoiding Permutations.- Folding a Better Checkerboard.- Finding All Approximate Gapped Palindromes.- General Pseudo-random Generators from Weaker Models of Computation.- Random Generation and Enumeration of Bipartite Permutation Graphs.- A Combinatorial Algorithm for Horn Programs.- Online Maximum Directed Cut.- Maintaining Nets and Net Trees under Incremental Motion.- Distributed Scheduling of Parallel Hybrid Computations.- I/O-Efficient Contour Tree Simplification.- Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes.- I/O and Space-Efficient Path Traversal in Planar Graphs.- Improved Algorithms for Finding Consistent Superstrings Based on aNew Graph Model.- Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (…