Algorithms and Computation: 20th International Symposium, Isaac 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings (Paperback, 2009)

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.- Frechet 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 Planar Graphs.- 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 a New Graph Model.- Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract).- Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets.- On Partitioning a Graph into Two Connected Subgraphs.