Algorithms and Data Structures: 10th International Workshop, WADS 2007, Halifax, Canada, August 15-17, 2007. Proceedings

Jeff Erickson (auth.), Frank Dehne, Jörg-Rüdiger Sack, Norbert Zeh (eds.)3540739483, 9783540739487

The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 – 17, 2007, at Dalhousie University, Halifax, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT 1988 and WADS 1989. From 142 submissions, the Program Committee selected 54 papers for presentation at the workshop. In addition, invited lectures were given by the following dist- guished researchers: Je? Erickson (University of Illinois at Urbana-Champaign) and Mike Langston (University of Tennessee). On behalf of the Program Committee, we would like to express our sincere appreciation to the many persons whose e?ort contributed to making WADS 2007 a success. These include the invited speakers, members of the Steering and ProgramCommittees, the authorswho submitted papers, andthe manyreferees who assisted the Program Committee. We are indebted to Gerardo Reynaga for installing and modifying the submission software, maintaining the submission server and interacting with authors as well as for helping with the preparation of the program.

---

Table of contents :
Front Matter….Pages –
Finding Small Holes….Pages 1-1
Approximate Range Searching: The Absolute Model….Pages 2-14
Orthogonal Range Searching in Linear and Almost-Linear Space….Pages 15-26
Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere….Pages 27-38
A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity….Pages 39-51
Approximating the Maximum Sharing Problem….Pages 52-63
The Stackelberg Minimum Spanning Tree Game….Pages 64-76
Edges and Switches, Tunnels and Bridges….Pages 77-88
How to Draw a Clustered Tree….Pages 89-101
Drawing Colored Graphs on Colored Points….Pages 102-113
Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric….Pages 114-126
Priority Queues Resilient to Memory Faults….Pages 127-138
Simple and Space-Efficient Minimal Perfect Hash Functions….Pages 139-150
A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane….Pages 151-162
A Pseudopolynomial Time O (log n )-Approximation Algorithm for Art Gallery Problems….Pages 163-174
Optimization for First Order Delaunay Triangulations….Pages 175-187
Constant Factor Approximations for the Hotlink Assignment Problem….Pages 188-200
Approximation Algorithms for the Sex-Equal Stable Marriage Problem….Pages 201-213
A Stab at Approximating Minimum Subadditive Join….Pages 214-225
Algorithmic Challenges for Systems-Level Correlational Analysis: A Tale of Two Datasets….Pages 226-226
Flooding Countries and Destroying Dams….Pages 227-238
I/O-Efficient Flow Modeling on Fat Terrains….Pages 239-250
Computing the Visibility Map of Fat Objects….Pages 251-262
Independent Sets in Bounded-Degree Hypergraphs….Pages 263-274
Steiner Tree in Planar Graphs: An O ( n log n ) Approximation Scheme with Singly-Exponential Dependence on Epsilon….Pages 275-286
Computing a Minimum-Depth Planar Graph Embedding in O ( n 4 ) Time….Pages 287-299
On a Family of Strong Geometric Spanners That Admit Local Routing Strategies….Pages 300-311
Spanners for Geometric Intersection Graphs….Pages 312-324
On Generalized Diamond Spanners….Pages 325-336
The k -Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces….Pages 337-348
On the Robustness of Graham’s Algorithm for Online Scheduling….Pages 349-361
Improved Results for a Memory Allocation Problem….Pages 362-373
Computational and Structural Advantages of Circular Boundary Representation….Pages 374-385
Alpha-Beta Witness Complexes….Pages 386-397
Cauchy’s Theorem and Edge Lengths of Convex Polyhedra….Pages 398-409
Fixed-Parameter Tractability for Non-Crossing Spanning Trees….Pages 410-421
Improved Algorithms for the Feedback Vertex Set Problems….Pages 422-433
Kernelization Algorithms for d-Hitting Set Problems….Pages 434-445
Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points….Pages 446-457
Maximizing Maximal Angles for Plane Straight-Line Graphs….Pages 458-469
Cuttings for Disks and Axis-Aligned Rectangles….Pages 470-482
Kernelization and Complexity Results for Connectivity Augmentation Problems….Pages 483-494
An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem….Pages 495-506
Branch and Recharge: Exact Algorithms for Generalized Domination….Pages 507-518
On Computing the Centroid of the Vertices of an Arrangement and Related Problems….Pages 519-528
Optimal Algorithms for the Weighted p -Center Problems on the Real Line for Small p ….Pages 529-540
Faster Approximation of Distances in Graphs….Pages 541-552
Approximate Shortest Paths Guided by a Small Index….Pages 553-564
Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model….Pages 565-576
Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field….Pages 577-588
35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality….Pages 589-600
On Euclidean Vehicle Routing with Allocation….Pages 601-612
Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets….Pages 613-624
Range Non-overlapping Indexing and Successive List Indexing….Pages 625-636
Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton’s Identities and Invertible Bloom Filters….Pages 637-648
Dynamic TCP Acknowledgment with Sliding Window….Pages 649-660
Back Matter….Pages –