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.
Author(s): Ronald L. Graham (auth.), Yingfei Dong, Ding-Zhu Du, Oscar Ibarra (eds.)
Series: Lecture Notes in Computer Science 5878 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 1228
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Algorithms; Logics and Meanings of Programs; Numeric Computing; Mathematical Logic and Formal Languages
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 -
