List of accepted papers for WADS 2011:


Abhijin Adiga, Jasine Babu and L. Sunil Chandran. 
A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs 

Rolf Harren, Klaus Jansen, Lars Pradel and Rob Van Stee. 
A (5/3+\eps)-Approximation for Strip Packing 

Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Lena Schlipf and Shang Yang. 
Convex Transversals 

Therese Biedl and Lesvia Elena Ruiz Velazquez. 
Orthogonal cartograms with few corners per face 

Allan Jorgensen, Maarten Loffler and Jeff Phillips. 
Geometric Computations on Indecisive Points 

Johannes Fischer. 
Inducing the LCP-Array 

Niv Buchbinder, Moran Feldman, Arpita Ghosh and Seffi Naor. 
Frequency Capping in Online Advertising 

Yaw-Ling Lin, Charles Ward, Bharat Jain and Steven Skiena. 
Constructing Orthogonal de Bruijn Sequences 

Zhou Xu and Xiaofan Lai. 
A Fully Polynomial Approximation Scheme for a Knapsack Problem with a Minimum Filling Constraint 

Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos and Yngve Villanger. 
Enumerating Minimal Subset Feedback Vertex Sets 

Brent Heeringa, Marius Catalin Iordan and Louis Theran. 
Searching in Dynamic Tree-Like Partial Orders 

Markus Blaser, Bodo Manthey and B. V. Raghavendra Rao. 
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals 

Jianer Chen, Jia-Hao Fan, Iyad Kanj, Yang Liu and Fenghui Zhang. 
Multicut in trees viewed through the eyes of vertex cover 

David Eppstein, Michael Goodrich and Maarten Loffler. 
Tracking Moving Objects with Few Handovers 

Nikhil Devanur and Uriel Feige. 
An O(n log n) Algorithm for a Load Balancing Problem on Paths 

Michael Hoffmann, Micha Sharir, Adam Sheffer, Csaba Toth and Emo Welzl. 
Counting Plane Graphs: Flippability and its Applications 

Atlas F. Cook Iv, Anne Driemel, Sariel Har-Peled, Jessica Sherette and Carola Wenk. 
Computing the Frechet Distance Between Folded Polygons 

Mark De Berg, Amirali Khosravi, Sander Verdonschot and Vincent Van Der Weele. 
On Rectilinear Partitions with Minimum Stabbing Number 

Peter Damaschke and Leonid Molokov. 
Parameterized Reductions and Algorithms for Another Vertex Cover Generalization 

Boris Aronov and Muriel Dulieu. 
How to Cover a Point Set with a V-Shape of Minimum Width 

Tobias Christ. 
Beyond Triangulation: Covering Polygons with Triangles 

Therese Biedl, Stephane Durocher, Celine Engelbeen, Samuel Fiorini and Maxwell Young. 
Faster Optimal Algorithms For Segment Minimization With Small Maximal Value 

Yahav Nussbaum. 
Improved Distance Queries in Planar Graphs 

Boris Aronov, Muriel Dulieu and Ferran Hurtado. 
Witness Rectangle Graphs 

Valentin Polishchuk and Mikko Sysikaski. 
Faster algorithms for minimum-link paths with restricted orientations 

Ferdinando Cicalese, Tobias Jacobs, Eduardo Laber and Caio Valentim. 
Binary Identification Problems for Weighted Trees 

Anne Driemel, Herman Haverkort, Maarten Loffler and Rodrigo Silveira. 
Flow Computations on Imprecise Terrains 

Gruia Calinescu and Minming Li. 
Register Loading via Linear Programming 

Erin Chambers, Sandor Fekete, Hella-Franziska Hoffmann, Dimitri Marinakis, Joseph Mitchell, Venkatesh Srinivasan, Ulrike Stege and Sue Whitesides. 
Connecting a Set of Circles with Minimum Sum of Radii 

Danny Z. Chen and Haitao Wang. 
New Algorithms for 1-D Facility Location and Path Equipartition Problems 

Prosenjit Bose, Paz Carmi, Mirela Damian, Robin Flatland, Matthew Katz and Anil Maheshwari. 
Switching to Directional Antennas with Constant Increase in Radius and Hop Distance 

Jaikumar Radhakrishnan and Saswata Shannigrahi. 
Streaming algorithms for 2-coloring uniform hypergraphs 

P. Thomas Fletcher, John Moeller, Jeff Phillips and Suresh Venkatasubramanian. 
Horoball Hulls and Extents in Positive Definite Space 

Tim Nonner. 
PTAS for Densest k-Subgraph in Interval Graphs 

Yakov Nekrich. 
A Fast Algorithm for Three-Dimensional Layers of Maxima Problem 

Jing He, Hongyu Liang and Guang Yang. 
Reversing Longest Previous Factor Tables is Hard 

Beat Gfeller. 
Finding Longest Approximate Periodic Patterns 

Andreas Gemsa, Martin Nollenburg and Ignaz Rutter. 
Consistent Labeling of Rotating Maps 

Shoshana Neuburger and Dina Sokol. 
Succinct 2D Dictionary Matching With No Slowdown 

David Kirkpatrick and Sandra Zilles. 
Competitive search in symmetric trees 

Timothy M. Chan and Vinayak Pathak. 
Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions 

Mohammad Ali Abam, Mark De Berg and Amirali Khosravi. 
Piecewise-Linear Approximations of Uncertain Functions 

Jie Gao and Dengpan Zhou. 
Resilient and Low Stretch Routing Through Embedding into Tree Metrics 

Christof Doll, Tanja Hartmann and Dorothea Wagner. 
Fully-Dynamic Hierarchical Graph Clustering Using Cut Trees 

Spyros Angelopoulos, Alejandro Lopez-Ortiz and Konstantinos Panagiotou. 
Multi-target Ray Searching Problems 

Meng He and Ian Munro. 
Space Efficient Data Structures for Dynamic Orthogonal Range Counting 

Andrea Schumm, Robert Goerke and Dorothea Wagner. 
Density-Constrained Graph Clustering 

Kyle Fox. 
Upper Bounds for Maximally Greedy Binary Search Trees 

Shay Solomon. 
The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light 

Pegah Kamousi, Timothy Chan and Subhash Suri. 
Closest Pair and the Post Office Problem for Stochastic Points 

Paul Bonsma and Daniel Lokshtanov. 
Feedback Vertex Set in Mixed Graphs 

Evangelos Kranakis, Oscar Morales Ponce and Jukka Suomela. 
Planar Subgraphs without Low-Degree Nodes 

Kevin Buchin, David Eppstein, Maarten Loffler, Martin Nollenburg and Rodrigo Silveira. 
Adjacency-Preserving Spatial Treemaps 

Pooya Davoodi, Gerth Stolting Brodal and Srinivasa Rao Satti. 
Path Minima Queries in Dynamic Weighted Trees 

Philip Klein and Shay Mozes. 
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log n) Time 

Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann and Claudio Squarcella. 
On the Area Requirements of Euclidean Minimum Spanning Trees 

Paul Christiano, Erik D. Demaine and Shaunak Kishore. 
Lossless Fault-Tolerant Data Structures with Additive Overhead 

Erik D. Demaine and Sarah Eisenstat. 
Flattening Fixed-Angle Chains Is Strongly NP-Complete 

Michael Fredman. 
On the matter of dynamic optimality in an extended model for tree access operations