Ebook: Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings

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.

---

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.

---

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.

Content:
Front Matter....Pages -
Bubblesort and Juggling Sequences....Pages 1-1
A Proof of the Molecular Conjecture....Pages 2-3
Exact Algorithms for Dominating Clique Problems....Pages 4-13
Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming....Pages 14-23
Exact Algorithms for the Bottleneck Steiner Tree Problem....Pages 24-33
Exact Algorithms for Set Multicover and Multiset Multicover Problems....Pages 34-44
Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm....Pages 45-54
Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems....Pages 55-64
On Protein Structure Alignment under Distance Constraint....Pages 65-76
A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability....Pages 77-86
Max-Coloring Paths: Tight Bounds and Extensions....Pages 87-96
Fr?chet Distance Problems in Weighted Regions....Pages 97-111
The Complexity of Solving Stochastic Games on Graphs....Pages 112-121
Computational Complexity of Cast Puzzles....Pages 122-131
New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body....Pages 132-141
Reconstructing Numbers from Pairwise Function Values....Pages 142-152
Hilbert’s Thirteenth Problem and Circuit Complexity....Pages 153-162
Interval Stabbing Problems in Small Integer Ranges....Pages 163-172
Online Sorted Range Reporting....Pages 173-182
Data Structures for Approximate Orthogonal Range Counting....Pages 183-192
Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time....Pages 193-202
Untangled Monotonic Chains and Adaptive Range Search....Pages 203-212
Geodesic Spanners on Polyhedral Surfaces....Pages 213-223
Approximating Points by a Piecewise Linear Function: I....Pages 224-233
Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers....Pages 234-243
Computing the Map of Geometric Minimal Cuts....Pages 244-254
On the Camera Placement Problem....Pages 255-264
Graph Orientations with Set Connectivity Requirements....Pages 265-274
Geometric Minimum Diameter Minimum Cost Spanning Tree Problem....Pages 275-282
On Shortest Disjoint Paths in Planar Graphs....Pages 283-292
An Optimal Labeling for Node Connectivity....Pages 293-302
SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks....Pages 303-310
1-Bounded Space Algorithms for 2-Dimensional Bin Packing....Pages 311-320
On the Advice Complexity of Online Problems....Pages 321-330
Online Knapsack Problems with Limited Cuts....Pages 331-340
Online Paging for Flash Memory Devices....Pages 341-351
Shifting Strategy for Geometric Graphs without Geometry....Pages 352-361
Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics....Pages 362-371
Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time....Pages 372-382
Minimum Covering with Travel Cost....Pages 383-392
Route-Enabling Graph Orientation Problems....Pages 393-402
Complexity of Approximating the Vertex Centroid of a Polyhedron....Pages 403-412
Popular Matchings with Variable Job Capacities....Pages 413-422
On the Tightness of the Buhrman-Cleve-Wigderson Simulation....Pages 423-433
Bounds on Contention Management Algorithms....Pages 434-440
Algorithmic Folding Complexity....Pages 441-451
Min-Energy Scheduling for Aligned Jobs in Accelerate Model....Pages 452-461
Posi-modular Systems with Modulotone Requirements under Permutation Constraints....Pages 462-472
Generalized Reduction to Compute Toric Ideals....Pages 473-482
Linear and Sublinear Time Algorithms for Basis of Abelian Groups....Pages 483-492
Good Programming in Transactional Memory....Pages 493-502
Induced Packing of Odd Cycles in a Planar Graph....Pages 503-513
On the Infinitesimal Rigidity of Bar-and-Slider Frameworks....Pages 514-523
Exploration of Periodically Varying Graphs....Pages 524-533
Parameterized Complexity of Arc-Weighted Directed Steiner Problems....Pages 534-543
Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries....Pages 544-553
Minimum Cycle Bases of Weighted Outerplanar Graphs....Pages 554-563
Editing Graphs into Disjoint Unions of Dense Clusters....Pages 564-572
Parameterizing Cut Sets in a Graph by the Number of Their Components....Pages 573-582
Inapproximability of Maximal Strip Recovery....Pages 583-593
The Complexity of Perfect Matching Problems on Dense Hypergraphs....Pages 594-604
On Lower Bounds for Constant Width Arithmetic Circuits....Pages 605-615
Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria....Pages 616-625
The Identity Correspondence Problem and Its Applications....Pages 626-636
Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs....Pages 637-646
An Improved Approximation Algorithm for the Traveling Tournament Problem....Pages 647-656
The Fault-Tolerant Facility Allocation Problem....Pages 657-667
Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks....Pages 668-678
Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms....Pages 679-688
The Directed Hausdorff Distance between Imprecise Point Sets....Pages 689-698
Computing Multidimensional Persistence....Pages 699-709
Locating an Obnoxious Line among Planar Objects....Pages 710-719
Finding Fullerene Patches in Polynomial Time....Pages 720-729
A Self-stabilizing and Local Delaunay Graph Construction....Pages 730-739
Succinct Greedy Geometric Routing in the Euclidean Plane....Pages 740-749
Electric Routing and Concurrent Flow Cutting....Pages 750-759
A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths....Pages 760-770
Strong Robustness of Randomized Rumor Spreading Protocols....Pages 771-780
Data Structures for Range Median Queries....Pages 781-791
Deletion without Rebalancing in Multiway Search Trees....Pages 792-801
Counting in the Presence of Memory Faults....Pages 802-811
A Simple, Fast, and Compact Static Dictionary....Pages 812-821
Reconstructing Polygons from Scanner Data....Pages 822-831
Computing Large Matchings in Planar Graphs with Fixed Minimum Degree....Pages 832-841
Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs....Pages 842-851
Covering a Graph with a Constrained Forest (Extended Abstract)....Pages 852-861
Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs....Pages 862-871
Upward Star-Shaped Polyhedral Graphs....Pages 872-881
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract)....Pages 882-891
Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement....Pages 892-901
Step-Assembly with a Constant Number of Tile Types....Pages 902-912
Lower Bounds on Fast Searching....Pages 913-922
Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity....Pages 923-932
Optimal Randomized Algorithm for the Density Selection Problem....Pages 933-942
New Results on Simple Stochastic Games....Pages 943-953
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences....Pages 954-963
Succinct Index for Dynamic Dictionary Matching....Pages 964-973
Range Non-overlapping Indexing....Pages 974-983
Querying Two Boundary Points for Shortest Paths in a Polygonal Domain....Pages 984-993
Pattern Matching for 321-Avoiding Permutations....Pages 994-1003
Folding a Better Checkerboard....Pages 1004-1013
Finding All Approximate Gapped Palindromes....Pages 1014-1023
General Pseudo-random Generators from Weaker Models of Computation....Pages 1024-1033
Random Generation and Enumeration of Bipartite Permutation Graphs....Pages 1034-1043
A Combinatorial Algorithm for Horn Programs....Pages 1044-1053
Online Maximum Directed Cut....Pages 1054-1063
Maintaining Nets and Net Trees under Incremental Motion....Pages 1064-1073
Distributed Scheduling of Parallel Hybrid Computations....Pages 1074-1083
I/O-Efficient Contour Tree Simplification....Pages 1084-1093
Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes....Pages 1094-1103
I/O and Space-Efficient Path Traversal in Planar Graphs....Pages 1104-1113
Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model....Pages 1114-1123
Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract)....Pages 1124-1133
Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets....Pages 1134-1143
On Partitioning a Graph into Two Connected Subgraphs....Pages 1144-1154
Back Matter....Pages 1155-1165
....Pages 1166-1174