Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings

Front Matter....Pages -
On the Power of the Semi-Separated Pair Decomposition....Pages 1-12
Plane Graphs with Parity Constraints....Pages 13-24
Straight-Line Rectangular Drawings of Clustered Graphs....Pages 25-36
Online Priority Steiner Tree Problems....Pages 37-48
Connect the Dot: Computing Feed-Links with Minimum Dilation....Pages 49-60
Minimal Locked Trees....Pages 61-73
Approximating Transitive Reductions for Directed Networks....Pages 74-85
1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2....Pages 86-97
Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing....Pages 98-109
A Distribution-Sensitive Dictionary with Low Space Overhead....Pages 110-118
A Comparison of Performance Measures for Online Algorithms....Pages 119-130
Delaunay Triangulation of Imprecise Points Simplified and Extended....Pages 131-143
An Improved SAT Algorithm in Terms of Formula Length....Pages 144-155
Shortest Path Problems on a Polyhedral Surface....Pages 156-167
Approximation Algorithms for Buy-at-Bulk Geometric Network Design....Pages 168-180
Rank-Sensitive Priority Queues....Pages 181-192
Algorithms Meet Art, Puzzles, and Magic....Pages 193-193
Skip-Splay: Toward Achieving the Unified Bound in the BST Model....Pages 194-205
Drawing Graphs with Right Angle Crossings....Pages 206-217
Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance....Pages 218-229
Efficient Construction of Near-Optimal Binary and Multiway Search Trees....Pages 230-241
On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem....Pages 242-253
On Reconfiguration of Disks in the Plane and Related Problems....Pages 254-265
Orientation-Constrained Rectangular Layouts....Pages 266-277
The h -Index of a Graph and Its Application to Dynamic Subgraph Statistics....Pages 278-289
Optimal Embedding into Star Metrics....Pages 290-301
Online Square Packing....Pages 302-314
Worst-Case Optimal Adaptive Prefix Coding....Pages 315-326
New Results on Visibility in Simple Polygons....Pages 327-338
Dynamic Graph Clustering Using Minimum-Cut Trees....Pages 339-350
Rank-Balanced Trees....Pages 351-362
Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments....Pages 363-374
Reconfiguration of List Edge-Colorings in a Graph....Pages 375-386
The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs....Pages 387-398
Two for One: Tight Approximation of 2D Bin Packing....Pages 399-410
Fault Tolerant External Memory Algorithms....Pages 411-422
Inspecting a Set of Strips Optimally....Pages 423-434
A Pseudopolynomial Algorithm for Alexandrov’s Theorem....Pages 435-446
A Scheme for Computing Minimum Covers within Simple Regions....Pages 447-458
Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem....Pages 459-470
Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality....Pages 471-482
Streaming Embeddings with Slack....Pages 483-494
Computing the Implicit Voronoi Diagram in Triple Precision....Pages 495-506
Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms....Pages 507-518
Integer Programming: Optimization and Evaluation Are Equivalent....Pages 519-529
Resolving Loads with Positive Interior Stresses....Pages 530-541
On Making Directed Graphs Transitive....Pages 542-553
Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees....Pages 554-565
Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs....Pages 566-577
Back Matter....Pages -