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

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 -