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

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
A Linear Vertex Kernel for Maximum Internal Spanning Tree ....Pages 275-282
Geometric Minimum Diameter Minimum Cost Spanning Tree Problem....Pages 283-292
On Shortest Disjoint Paths in Planar Graphs....Pages 293-302
An Optimal Labeling for Node Connectivity....Pages 303-310
SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks....Pages 311-320
1-Bounded Space Algorithms for 2-Dimensional Bin Packing....Pages 321-330
On the Advice Complexity of Online Problems....Pages 331-340
Online Knapsack Problems with Limited Cuts....Pages 341-351
Online Paging for Flash Memory Devices....Pages 352-361
Shifting Strategy for Geometric Graphs without Geometry....Pages 362-371
Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics....Pages 372-382
Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time....Pages 383-392
Minimum Covering with Travel Cost....Pages 393-402
Route-Enabling Graph Orientation Problems....Pages 403-412
Complexity of Approximating the Vertex Centroid of a Polyhedron....Pages 413-422
Popular Matchings with Variable Job Capacities....Pages 423-433
On the Tightness of the Buhrman-Cleve-Wigderson Simulation....Pages 434-440
Bounds on Contention Management Algorithms....Pages 441-451
Algorithmic Folding Complexity....Pages 452-461
Min-Energy Scheduling for Aligned Jobs in Accelerate Model....Pages 462-472
Posi-modular Systems with Modulotone Requirements under Permutation Constraints....Pages 473-482
Generalized Reduction to Compute Toric Ideals....Pages 483-492
Linear and Sublinear Time Algorithms for Basis of Abelian Groups....Pages 493-502
Good Programming in Transactional Memory....Pages 503-513
Induced Packing of Odd Cycles in a Planar Graph....Pages 514-523
On the Infinitesimal Rigidity of Bar-and-Slider Frameworks....Pages 524-533
Exploration of Periodically Varying Graphs....Pages 534-543
Parameterized Complexity of Arc-Weighted Directed Steiner Problems....Pages 544-553
Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries....Pages 554-563
Minimum Cycle Bases of Weighted Outerplanar Graphs....Pages 564-572
 Bandwidth on AT-Free Graphs....Pages 573-582
Editing Graphs into Disjoint Unions of Dense Clusters....Pages 583-593
A Certifying Algorithm for 3-Colorability of P 5 -Free Graphs....Pages 594-604
Parameterizing Cut Sets in a Graph by the Number of Their Components....Pages 605-615
Inapproximability of Maximal Strip Recovery....Pages 616-625
The Complexity of Perfect Matching Problems on Dense Hypergraphs....Pages 626-636
On Lower Bounds for Constant Width Arithmetic Circuits....Pages 637-646
Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria....Pages 647-656
The Identity Correspondence Problem and Its Applications....Pages 657-667
Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs....Pages 668-678
An Improved Approximation Algorithm for the Traveling Tournament Problem....Pages 679-688
The Fault-Tolerant Facility Allocation Problem....Pages 689-698
Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks....Pages 699-709
Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms....Pages 710-719
The Directed Hausdorff Distance between Imprecise Point Sets....Pages 720-729
Computing Multidimensional Persistence....Pages 730-739
Locating an Obnoxious Line among Planar Objects....Pages 740-749
Finding Fullerene Patches in Polynomial Time....Pages 750-759
Convex Drawings of Internally Triconnected Plane Graphs on O ( n 2 ) Grids....Pages 760-770
A Self-stabilizing and Local Delaunay Graph Construction....Pages 771-780
Succinct Greedy Geometric Routing in the Euclidean Plane....Pages 781-791
Electric Routing and Concurrent Flow Cutting....Pages 792-801
A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths....Pages 802-811
Strong Robustness of Randomized Rumor Spreading Protocols....Pages 812-821
Data Structures for Range Median Queries....Pages 822-831
Deletion without Rebalancing in Multiway Search Trees....Pages 832-841
Counting in the Presence of Memory Faults....Pages 842-851
A Simple, Fast, and Compact Static Dictionary....Pages 852-861
Reconstructing Polygons from Scanner Data....Pages 862-871
Computing Large Matchings in Planar Graphs with Fixed Minimum Degree....Pages 872-881
Crossing-Free Acyclic Hamiltonian Path Completion for Planar st -Digraphs....Pages 882-891
Covering a Graph with a Constrained Forest (Extended Abstract)....Pages 892-901
Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs....Pages 902-912
Upward Star-Shaped Polyhedral Graphs....Pages 913-922
Conditional Hardness of Approximating Satisfiable Max 3CSP- q ....Pages 923-932
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract)....Pages 933-942
Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement....Pages 943-953
Step-Assembly with a Constant Number of Tile Types....Pages 954-963
Lower Bounds on Fast Searching....Pages 964-973
Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity....Pages 974-983
Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O ( n 1 + ε ) Time....Pages 984-993
PTAS for k -Tour Cover Problem on the Plane for Moderately Large Values of  k ....Pages 994-1003
Optimal Randomized Algorithm for the Density Selection Problem....Pages 1004-1013
New Results on Simple Stochastic Games....Pages 1014-1023
Worst-Case and Smoothed Analysis of k -Means Clustering with Bregman Divergences....Pages 1024-1033
Succinct Index for Dynamic Dictionary Matching....Pages 1034-1043
Range Non-overlapping Indexing....Pages 1044-1053
Querying Two Boundary Points for Shortest Paths in a Polygonal Domain....Pages 1054-1063
Pattern Matching for 321-Avoiding Permutations....Pages 1064-1073
Folding a Better Checkerboard....Pages 1074-1083
Finding All Approximate Gapped Palindromes....Pages 1084-1093
General Pseudo-random Generators from Weaker Models of Computation....Pages 1094-1103
Random Generation and Enumeration of Bipartite Permutation Graphs....Pages 1104-1113
A Combinatorial Algorithm for Horn Programs....Pages 1114-1123
Online Maximum Directed Cut....Pages 1124-1133
Maintaining Nets and Net Trees under Incremental Motion....Pages 1134-1143
Distributed Scheduling of Parallel Hybrid Computations....Pages 1144-1154
I/O-Efficient Contour Tree Simplification....Pages 1155-1165
Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes....Pages 1166-1174
I/O and Space-Efficient Path Traversal in Planar Graphs....Pages 1175-1184
Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model....Pages 1185-1194
Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract)....Pages 1195-1204
Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets....Pages 1205-1214
On Partitioning a Graph into Two Connected Subgraphs....Pages 1215-1224
Back Matter....Pages -