Algorithms and Data Structures: 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings

Front Matter....Pages -
Piecewise-Linear Approximations of Uncertain Functions....Pages 1-12
A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs....Pages 13-24
On the Area Requirements of Euclidean Minimum Spanning Trees....Pages 25-36
Multi-target Ray Searching Problems....Pages 37-48
Convex Transversals....Pages 49-60
How to Cover a Point Set with a V-Shape of Minimum Width....Pages 61-72
Witness Rectangle Graphs....Pages 73-85
Faster Optimal Algorithms for Segment Minimization with Small Maximal Value....Pages 86-97
Orthogonal Cartograms with Few Corners Per Face....Pages 98-109
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals....Pages 110-121
Feedback Vertex Set in Mixed Graphs....Pages 122-133
Switching to Directional Antennas with Constant Increase in Radius and Hop Distance....Pages 134-146
Frequency Capping in Online Advertising....Pages 147-158
Adjacency-Preserving Spatial Treemaps....Pages 159-170
Register Loading via Linear Programming....Pages 171-182
Connecting a Set of Circles with Minimum Sum of Radii....Pages 183-194
Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions....Pages 195-206
New Algorithms for 1-D Facility Location and Path Equipartition Problems....Pages 207-218
Multicut in Trees Viewed through the Eyes of Vertex Cover....Pages 219-230
Beyond Triangulation: Covering Polygons with Triangles....Pages 231-242
Lossless Fault-Tolerant Data Structures with Additive Overhead....Pages 243-254
Binary Identification Problems for Weighted Trees....Pages 255-266
Computing the Fréchet Distance between Folded Polygons....Pages 267-278
Parameterized Reductions and Algorithms for Another Vertex Cover Generalization....Pages 279-289
Path Minima Queries in Dynamic Weighted Trees....Pages 290-301
On Rectilinear Partitions with Minimum Stabbing Number....Pages 302-313
Flattening Fixed-Angle Chains Is Strongly NP-Hard....Pages 314-325
An O ( n log n ) Algorithm for a Load Balancing Problem on Paths....Pages 326-337
Fully-Dynamic Hierarchical Graph Clustering Using Cut Trees....Pages 338-349
Flow Computations on Imprecise Terrains....Pages 350-361
Tracking Moving Objects with Few Handovers....Pages 362-373
Inducing the LCP-Array....Pages 374-385
Horoball Hulls and Extents in Positive Definite Space....Pages 386-398
Enumerating Minimal Subset Feedback Vertex Sets....Pages 399-410
Upper Bounds for Maximally Greedy Binary Search Trees....Pages 411-422
On the Matter of Dynamic Optimality in an Extended Model for Tree Access Operations....Pages 423-437
Resilient and Low Stretch Routing through Embedding into Tree Metrics....Pages 438-450
Consistent Labeling of Rotating Maps....Pages 451-462
Finding Longest Approximate Periodic Patterns....Pages 463-474
A (5/3 +  ε )-Approximation for Strip Packing....Pages 475-487
Reversing Longest Previous Factor Tables is Hard....Pages 488-499
Space Efficient Data Structures for Dynamic Orthogonal Range Counting....Pages 500-511
Searching in Dynamic Tree-Like Partial Orders....Pages 512-523
Counting Plane Graphs: Flippability and Its Applications....Pages 524-535
Geometric Computations on Indecisive Points....Pages 536-547
Closest Pair and the Post Office Problem for Stochastic Points....Pages 548-559
Competitive Search in Symmetric Trees....Pages 560-570
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O (diameter · n log n ) Time....Pages 571-582
Planar Subgraphs without Low-Degree Nodes....Pages 583-594
Constructing Orthogonal de Bruijn Sequences....Pages 595-606
A Fast Algorithm for Three-Dimensional Layers of Maxima Problem....Pages 607-618
Succinct 2D Dictionary Matching with No Slowdown....Pages 619-630
PTAS for Densest k -Subgraph in Interval Graphs....Pages 631-641
Improved Distance Queries in Planar Graphs....Pages 642-653
Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers....Pages 654-654
Faster Algorithms for Minimum-Link Paths with Restricted Orientations....Pages 655-666
Streaming Algorithms for 2-Coloring Uniform Hypergraphs....Pages 667-678
Density-Constrained Graph Clustering....Pages 679-690
The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light....Pages 691-702
Theory vs. Practice in the Design and Analysis of Algorithms....Pages 703-703
A Fully Polynomial Approximation Scheme for a Knapsack Problem with a Minimum Filling Constraint....Pages 704-715
Back Matter....Pages -