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

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- di...

Full description

Bibliographic Details
Other Authors: Dehne, Frank (Editor), Sack, Jörg-Rüdiger (Editor), Zeh, Norbert (Editor)
Format: eBook
Language:English
Published: Berlin, Heidelberg Springer Berlin Heidelberg 2007, 2007
Edition:1st ed. 2007
Series:Theoretical Computer Science and General Issues
Subjects:
Online Access:
Collection: Springer eBooks 2005- - Collection details see MPG.ReNa
Table of Contents:
  • 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
  • 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-overlappingIndexing 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
  • 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
  • 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