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...
Other Authors: | , , |
---|---|
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