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

Session 1.- Finding Small Holes.- Session 2A.- Approximate Range Searching: The Absolute Model.- Orthogonal Range Searching in Linear and Almost-Linear Space.- Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere.- Session 2B.- A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity.- Approximating the Maximum Sharing Problem.- The Stackelberg Minimum Spanning Tree Game.- Session 3A.- Edges and Switches, Tunnels and Bridges.- How to Draw a Clustered Tree.- Drawing Colored Graphs on Colored Points.- Session 3B.- Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric.- Priority Queues Resilient to Memory Faults.- Simple and Space-Efficient Minimal Perfect Hash Functions.- Session 4A.- A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane.- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems.- Optimization for First Order Delaunay Triangulations.- Session 4B.- Constant Factor Approximations for the Hotlink Assignment Problem.- Approximation Algorithms for the Sex-Equal Stable Marriage Problem.- A Stab at Approximating Minimum Subadditive Join.- Session 5.- Algorithmic Challenges for Systems-Level Correlational Analysis: A Tale of Two Datasets.- Session 6A.- Flooding Countries and Destroying Dams.- I/O-Efficient Flow Modeling on Fat Terrains.- Computing the Visibility Map of Fat Objects.- Session 6B.- Independent Sets in Bounded-Degree Hypergraphs.- Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon.- Computing a Minimum-Depth Planar Graph Embedding in O(n 4) Time.- Session 7A.- On a Family of Strong Geometric Spanners That Admit Local Routing Strategies.- Spanners for Geometric Intersection Graphs.- On Generalized Diamond Spanners.- Session 7B.- The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces.- On the Robustness of Graham's Algorithm for Online Scheduling.- Improved Results for a Memory Allocation Problem.- Session 8A.- Computational and Structural Advantages of Circular Boundary Representation.- Alpha-Beta Witness Complexes.- Cauchy's Theorem and Edge Lengths of Convex Polyhedra.- Session 8B.- Fixed-Parameter Tractability for Non-Crossing Spanning Trees.- Improved Algorithms for the Feedback Vertex Set Problems.- Kernelization Algorithms for d-Hitting Set Problems.- Session 9A.- Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points.- Maximizing Maximal Angles for Plane Straight-Line Graphs.- Cuttings for Disks and Axis-Aligned Rectangles.- Session 9B.- Kernelization and Complexity Results for Connectivity Augmentation Problems.- An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem.- Branch and Recharge: Exact Algorithms for Generalized Domination.- Session 10A.- On Computing the Centroid of the Vertices of an Arrangement and Related Problems.- Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p.- Session 10B.- Faster Approximation of Distances in Graphs.- Approximate Shortest Paths Guided by a Small Index.- Session 11A.- Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model.- Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field.- 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality.- On Euclidean Vehicle Routing with Allocation.- Session 11B.- Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets.- Range Non-overlapping Indexing and Successive List Indexing.- Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton's Identities and Invertible Bloom Filters.- Dynamic TCP Acknowledgment with Sliding Window.