Mohammad Ali Abam, Paz Carmi, Mohammad Farshi (auth.), Frank Dehne, Marina Gavrilova, Jörg-Rüdiger Sack, Csaba D. Tóth (eds.)3642033660, 9783642033667
This book constitutes the refereed proceedings of the 11th Algorithms and Data Structures Symposium, WADS 2009, held in Banff, Canada, in August 2009.
The Algorithms and Data Structures Symposium – WADS (formerly “Workshop on Algorithms and Data Structures”) is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 49 revised full papers presented in this volume were carefully reviewed and selected from 126 submissions. The papers present original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.
Table of contents :
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 –
Reviews
There are no reviews yet.