Algorithms and Data Structures
12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011, Proceedings
Published on 18. July 2011
XV, 718 pages
978-3-642-22300-6 (ISBN)
Description
This book constitutes the refereed proceedings of the 12th Algorithms and Data Structures Symposium, WADS 2011, held in New York, NY, USA, in August 2011.
The Algorithms and Data Structures Symposium - WADS (formerly "Workshop on Algorithms and Data Structures") is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 59 revised full papers presented in this volume were carefully reviewed and selected from 141 submissions. The papers present original research on the theory and application of algorithms and data structures in all areas, including combinatorics, computational geometry, databases, graphics, parallel and distributed computing.
The Algorithms and Data Structures Symposium - WADS (formerly "Workshop on Algorithms and Data Structures") is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 59 revised full papers presented in this volume were carefully reviewed and selected from 141 submissions. The papers present original research on the theory and application of algorithms and data structures in all areas, including combinatorics, computational geometry, databases, graphics, parallel and distributed computing.
More details
Other editions
Additional editions
Frank Dehne | John Iacono | Jörg-Rüdiger Sack
Algorithms and Data Structures
12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011, Proceedings
Book
07/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Piecewise-Linear Approximations of Uncertain Functions
- Introduction
- The min-$k$ Problem
- The min-e Problem
- References
- A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs
- Introduction
- Preliminaries
- Notations
- A Vertex Numbering Scheme for Circular Arc Graphs
- Computing the Boxicity of Co-bipartite CA Graphs in Polynomial Time
- Reducing the Time Complexity of Computing the Boxicity of Co-bipartite CA Graphs
- Constant Factor Approximation for the Boxicity of CA Graphs
- Additive 2-Factor Approximation for the Boxicity of Normal CA Graphs
- References
- On the Area Requirements of Euclidean Minimum Spanning Trees
- Introduction
- Preliminaries
- Geometric Lemmata
- Angles and Edge Lengths in MST Embeddings
- The Proof of the Area Bound
- Conclusions
- References
- Multi-target Ray Searching Problems
- Introduction
- Ray Search in the Full-Information Model
- Ray-Search in the Partial-Information Model
- Intrinsic Cost of Multi-target Search
- A $O(logm)$-Competitive Algorithm
- An Asymptotically Optimal Multi-target Search Algorithm
- Conclusions
- References
- Convex Transversals
- Introduction
- Hardness Results
- Stabbing Segments in the Plane is NP-Hard
- Extensions
- Stabbing Disjoint Segments and Convex Pseudodisks
- Convexification
- Stabbing with Vertices of a Regular Polygon
- Polynomial-Time Algorithm
- Optimization Problem: Symmetry with Imprecision
- References
- How to Cover a Point Set with a V-Shape of Minimum Width
- Introduction
- Reduction to Canonical V-Shapes
- Computing a Canonical Minimum-Width V-Shape
- A 13-Approximation Algorithm
- Minimum-Width V-Shape for Points on Two Lines
- A (1 + e)-Approximation Algorithm
- Concluding Remarks
- References
- Witness Rectangle Graphs
- Introduction
- Structure of Witness Rectangle Graphs
- Two Connected Components
- What Are Staircase Graphs, Really?
- How to Stab Rectangles, Thriftily
- References
- Faster Optimal Algorithms for Segment Minimization with Small Maximal Value
- Introduction
- Single-Row Segmentation
- Full-Matrix Segmentation
- Segmenting a Row under Constraints
- Full-Matrix
- Further Improvements of the Complexity
- Solving the Lex-Min Problem
- The Special Case of $H = 2$
- Single Row for $H = 2$
- Full Matrix Segmentation for $H = 2$
- Conclusion
- References
- Orthogonal Cartograms with Few Corners Per Face
- Introduction
- Background and Preliminaries
- Dart-Shaped Graphs
- Algorithm for Orthogonal Cartograms
- T-Staircases
- Decomposing T-Staircases
- Pinning Dart-Shaped Graphs to T-Staircases
- Remarks
- References
- Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
- Introduction
- Preliminaries
- Euclidean Functionals
- Smoothed Analysis
- Framework
- Smoothed Running-Time
- Smoothed Approximation Ratio
- Matching
- Smoothed Running-Time
- Smoothed Approximation Ratio
- Karp's Partitioning Scheme for Euclidean TSP
- Euclidean Steiner Trees
- Degree-Bounded Minimum Spanning Tree
- Concluding Remarks
- References
- Feedback Vertex Set in Mixed Graphs
- Introduction
- Preliminaries
- Outline of the Algorithm
- An Algorithm for FVS/UMC: Reduction to Skew Separator
- An Algorithm for S-Disjoint FVS: Contracting Paths
- Discussion
- References
- Switching to Directional Antennas with Constant Increase in Radius and Hop Distance
- Introduction
- a = p/3
- a = p/3
- PointsalongaPath
- References
- Frequency Capping in Online Advertising (Extended Abstract)
- Introduction
- Related Work
- Preliminaries
- Identical Valuations
- Equal Demand Case
- General Case
- Equal Demands/Arbitrary Valuations
- Arbitrary Valuations
- A Primal-Dual Algorithm
- Further Directions
- References
- Adjacency-Preserving Spatial Treemaps
- Introduction
- Preliminaries
- Preserving Orientations
- Given the Global Layout
- Unconstrained Global Layout
- Without Preserving Orientations
- References
- Register Loading via Linear Programming
- Introduction
- Reduction
- 1-BSIM
- LP Rounding
- $k$-BSIM
- Conclusion
- References
- Connecting a Set of Circles with Minimum Sum of Radii
- Introduction
- CRA for a Given Connectivity Tree
- Range Assignment for Bounded Radii
- Solutions with a Bounded Number of Circles
- Polynomial-Time Approximation Schemes
- Unbounded Radii
- Bounded Radii
- Experimental Results
- Conclusion
- References
- Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions
- Introduction
- Streaming MEB
- Preliminaries and Agarwal and Sharathkumar's Algorithm
- An Improved Analysis
- Proof of Factor 4/3
- Proof of Factor 16/13
- Proof of Factor 1.22
- Dynamic MEB
- Preliminaries and a Dynamic Coreset Technique
- A New Dynamic Algorithm
- Final Remarks
- References
- New Algorithms for 1-D Facility Location and Path Equipartition Problems
- Introduction
- Related Work
- The Problem Modeling of the Facility Location
- The $k$-Median Problem
- The Infinity $k$-Coverage Problem
- The Linear Model
- The Path Equipartition Problems
- References
- Multicut in Trees Viewed through the Eyes of Vertex Cover
- Introduction
- Preliminaries
- The Kernel
- The Algorithm
- References
- Beyond Triangulation: Covering Polygons with Triangles
- Introduction
- NP-Hardness of the Triangle Cover Problem
- Inapproximability
- Covering without Steiner Points
- Covering the Boundary
- References
- Lossless Fault-Tolerant Data Structures with Additive Overhead
- Introduction
- Fundamental Techniques
- Blocked Fault-Tolerant Data Structures
- Fault-Resistant Operations
- Fault-Tolerant Operations
- Fault-Tolerant Memory
- Fault-Tolerant Predecessor
- Suffix Trees
- Fault-Resistant Tries
- Fault-Tolerant Suffix Trees
- Interval Trees
- References
- Binary Identification Problems for Weighted Trees
- Introduction
- Proofs of Strong NP-Hardness
- A Polynomial Time Algorithm for Diameter 5 Instances
- A Quadratic Time Algorithm for Path Instances
- An $o(logn)$ Approximation Algorithm
- References
- Computing the Fr´echet Distance between Folded Polygons
- Introduction
- Preliminaries
- Simple Polygons Algorithm Summary
- Shortest Path Edge Sequences
- Diagonal Monotonicity Test and Untangleability
- Fixed-Parameter Tractable Algorithm
- Untangleability Space
- Fixed-Parameter Tractable Algorithm
- Constant Factor Approximation Algorithm
- Axis-Parallel Folds and $L8$ Distance
- Future Work
- References
- Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
- Introduction
- Some Equivalent Parameterized Graph Editing Problems
- Solving Star Editing Faster than 3-Hitting Set
- Open Questions
- References
- Path Minima Queries in Dynamic Weighted Trees
- Introduction
- Previous Work
- Our Results
- Preliminaries
- Data Structures for Dynamic Weights
- Comparison-Based Data Structure
- RAM Structure
- Data Structures for Dynamic Leaves
- Optimal Semigroup Structure
- RAM Structure
- Lower Bounds
- References
- On Rectilinear Partitions with Minimum Stabbing Number
- Introduction
- Finding Optimal Rectilinear r-Partitions Is NP-Hard
- Polynomial Time Algorithms for Constant r
- Arbitrary versus Disjoint Rectilinear r-Partitions
- Experimental Results
- Results of the Comparisons
- Conclusion
- References
- Flattening Fixed-Angle Chains Is Strongly NP-Hard
- Introduction
- Definitions
- Linkages
- Rectilinear Planar Monotone 3-SAT
- Flattening Semi-rigid Chains
- Flattening Fixed-Angle Chains and Trees
- Flat Span
- References
- An $O(n log n)$ Algorithm for a Load Balancing Problem on Paths
- Introduction
- Preliminaries
- Hydraulic Apparatus
- An $O(n log n )$ Algorithm
- Conclusion and Open Problems
- References
- Fully-Dynamic Hierarchical Graph Clustering Using Cut Trees
- Introduction
- Preliminaries and Notation
- The Static Hierarchical Clustering Algorithm
- Update Algorithm for Dynamic Clustering Hierarchies
- Conclusion
- References
- Flow Computations on Imprecise Terrains
- Introduction
- NP-Hardness in the Surface Model
- Watersheds in the Network Model
- Potential Watersheds
- Core Watersheds
- Persistent Watersheds - An Alternative Definition
- Potential Downstream Areas
- Conclusions
- References
- Tracking Moving Objects with Few Handovers
- Introduction
- Problem Statement and Notation
- Offline Tracking
- Online Tracking
- Lower Bounds
- Trilateration
- Conclusions
- References
- Inducing the LCP-Array
- Introduction
- Previous Work and Concepts
- Suffix- and LCP-Arrays
- Constructing Suffix Arrays by Induced Sorting
- Inducing the LCP-Array
- Basic Algorithm
- Finding Minima
- Computing LCP-Values of S*-Suffixes
- Computing LCP-Values at the L/S-Seam
- Experimental Results
- Conclusions and Outlook
- References
- Horoball Hulls and Extents in Positive Definite Space
- Introduction
- Hulls and Convexity: From $R^d to P(n)$
- Technical Overview
- Related Work
- Preliminaries
- Busemann Functions and Horoballs
- Ball Hulls
- The e -Ball Hull
- Constructing the e -Ball Hull
- Decomposing P($n$) into Flats
- A Lipschitz Bound in P(2)
- Generalizing to P($n$)
- Algorithm
- References
- Enumerating Minimal Subset Feedback Vertex Sets
- Introduction
- Preliminaries
- Enumeration of All Minimal Subset Feedback Vertex Sets
- Running Time
- Concluding Remarks
- References
- Upper Bounds for Maximally Greedy Binary Search Trees
- Introduction
- A Geometric View
- Being Greedy
- Our Contributions
- A Note on Independent Work
- Arboral and Geometric Models of BSTs
- The Arboral Model
- The Geometric Model
- GreedyFuture
- An Access Lemma and Its Corollaries
- Potentials and Neighborhoods
- Immediate Consequences
- Telescoping Rank Changes
- Counting Stubborn Elements
- Finishing the Proof
- A Sequential Access Theorem
- Closing Remarks
- References
- On the Matter of Dynamic Optimality in an Extended Model for Tree Access Operations
- Introduction
- Technical Development
- Outline
- Existence of the Permutation
- Linear Off-Line Implementation
- Some Remarks
- References
- Resilient and Low Stretch Routing through Embedding into Tree Metrics
- Introduction
- Preliminaries
- Constant Distortion Routing Using Two HSTs
- Resilience to Node Failures Using Two HSTs
- Simulations
- References
- Consistent Labeling of Rotating Maps
- Introduction
- Model
- Properties of Consistent Labelings
- Complexity
- Basic Building Blocks
- Gadgets of the Reduction
- Approximation Algorithms
- A 1/4-Approximation for MaxTotal
- An Efficient Polynomial-Time Approximation Scheme for MaxTotal
- References
- Finding Longest Approximate Periodic Patterns
- Introduction and Related Work
- Optimal Algorithm for Absolute Error Periodic Patterns
- Algorithms for Relative Error Periodic Patterns
- An Exact Algorithm
- A Basic Approximate Algorithm
- An Approximate $O(n1+?)$Time Algorithm
- Solving Approximate 3SUM in $O(n1+?+Tsort(n))$ Time
- References
- A (5/3 + e)-Approximation for Strip Packing
- Introduction
- Overview of the Algorithm
- Item of Height Greater than 1/3
- One Special Big Item in $P$
- Overview of the Cases
- References
- Reversing Longest Previous Factor Tables is Hard
- Introduction
- Preliminaries
- Notations and Definitions
- Simple Properties of LPF Tables
- Reduction from 3-SAT
- Variable Section
- Assignment Section
- Checking Section
- LPF Tables with 0-1 Entries
- References
- Space Efficient Data Structures for Dynamic Orthogonal Range Counting
- Introduction
- Our Results
- Data Structures for Range Sum
- Range Sum in a Small Two-Dimensional Array
- Range Sum in a Narrow Two-Dimensional Array
- Range Counting in Integer Sequences
- Sequences of Small Integers
- General Integer Sequences
- Range Counting in Planar Point Sets
- Range Counting on a U × U Grid
- Range Counting for General Point Sets
- Concluding Remarks
- References
- Searching in Dynamic Tree-Like Partial Orders
- Introduction
- Models and Definitions
- Line-Leaf Tree Construction and Analysis
- Operations
- Empirical Results
- References
- Counting Plane Graphs: Flippability and Its Applications
- Introduction
- Applications of Ps-Flippable Edges
- The Ratio between the Number of Crossing-Free Straight-Edge Graphs and the Number of Triangulations
- The Number of Spanning Trees and Forests
- The Number of Crossing-Free Straight-Edge Graphs with a Bounded Number of Edges
- Conclusion
- References
- Geometric Computations on Indecisive Points
- Introduction
- Exact Computations on Indecisive Point Sets
- Polynomial Time Algorithms
- Hardness Results
- Approximate Computations on Uncertain Points
- References
- Closest Pair and the Post Office Problem for Stochastic Points
- Introduction
- The Stochastic Closest Pair Problem
- Counting Vertex Covers in Unit Disk Graphs
- Bichromatic Unit Disk Graphs
- Complexity of the Stochastic Closest Pair Problem
- Linearly Separable Point Sets under the L Norm
- Stochastic Approximate Nearest Neighbor Queries
- Approximation via a Modified Distance Function $^~l$
- The Data Structure: A BBD Tree
- An Exact Query Algorithm for $^~l$
- References
- Competitive Search in Symmetric Trees
- Introduction
- Symmetric Tree Traversal
- The Case Where All Goals Are Known to Lie at the Same Level
- Worst-Case Probe Cost
- Average and Expected-Case Probe Cost
- Taking Full Search Cost into Consideration
- The Case Where Goals May Appear on Many Different Levels
- General Symmetric Trees
- References
- Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in $O(diameter · n log n)$ Time
- Introduction
- Applications
- Related Work
- Preliminaries
- Flow
- Quasi-Feasible Flows and Negative-Length Dual Cycles
- The Algorithm
- Correctness and Analysis
- References
- Planar Subgraphs without Low-Degree Nodes
- Introduction
- Orientation Problem on Planar Circuit Networks
- Degree One
- Degree Two
- Degree Three
- Augmenting with Bounded Length Edges
- Conclusions
- References
- Constructing Orthogonal de Bruijn Sequences
- Introduction
- Preliminaries
- Kautz Graphs
- Analytical Results
- Special Orthogonal Families
- Counting Eulerians
- Heuristic Construction of Orthogonal Sequences
- Open Problems
- References
- A Fast Algorithm for Three-Dimensional Layers of Maxima Problem
- Introduction
- Sweep Plane Algorithm
- Fast Queries, Slow Updates
- Additional Staircases
- Efficient Algorithms for the Layers-of-Maxima Problem
- References
- Succinct 2D Dictionary Matching with No Slowdown
- Introduction
- Overview
- Preliminaries
- The Algorithm
- Pattern Preprocessing
- Text Scanning
- Conclusion
- References
- PTAS for Densest $k$-Subgraph in Interval Graphs
- Introduction
- Preliminaries
- Sequence Representations
- Simple Sequence Representations
- Dynamic Programming
- References
- Improved Distance Queries in Planar Graphs
- Introduction
- Preliminaries
- Decomposition
- The Dense Distance Graph
- The Monge Property
- Linear-Space Data Structure
- Improved Preprocessing Time for $S ? [n4/3, n2]$
- Improved Query Time for $S ? [n4/3, n2]$
- The Preprocessing Algorithm
- The Query Algorithm
- References
- Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers
- Faster Algorithms for Minimum-Link Paths with Restricted Orientations
- Introduction
- 3D Rectilinear Paths
- C-oriented Paths in the Plane
- Contributions
- Rectilinear Paths Amidst Rectilinear Obstacles in $R^3$
- Avoiding Reillumination
- Filtering
- Analysis
- $C$-oriented Paths in the Plane
- Overview
- Definitions and Notation
- Flush-Lighting
- Straddle-Lighting
- Analysis
- References
- Streaming Algorithms for 2-Coloring Uniform Hypergraphs
- Introduction
- Open Questions
- The Delayed Recoloring Algorithm
- An Efficient Streaming Algorithm
- Coloring Uniform Hypergraphs with O(n2lnn) Vertices
- Streaming and the Lovász Local Lemma
- References
- Density-Constrained Graph Clustering
- Introduction
- Quality Measures for Clusterings
- Problem Statement
- Complexity
- Generic Greedy Agglomeration
- Merge Behavior
- Impact of Clustering Measures on Running Times
- Concluding Remarks
- References
- The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light
- Introduction
- The MST of Symmetric Disk Graphs
- The Range Assignment Problem
- Proof Overview
- Related Work on Disk Graphs
- Structure of the Paper
- Preliminaries
- The MST of SDGs is Light
- The Range Assignment Problem
- References
- Theory vs. Practice in the Design and Analysis of Algorithms
- A Fully Polynomial Approximation Scheme for a Knapsack Problem with a Minimum Filling Constraint
- Introduction
- Related Works
- Our Results, Techniques, and Paper Outline
- Separations of Items
- Partial Search Procedure
- Computing $L$ and $U$
- FPTAS
- References
- Author Index
