Accepted Papers

  • Abhijin Adiga, Jasine Babu and L. Sunil Chandran. A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs
  • Rolf Harren, Klaus Jansen, Lars Prädel 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 Velázquez. Orthogonal cartograms with few corners per face
  • Allan Jorgensen, Maarten Löffler 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 Cătălin Iordan and Louis Theran. Searching in Dynamic Tree-Like Partial Orders
  • Markus Bläser, 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 Löffler. 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 Fréchet 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 Löffler 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 Nöllenburg 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 Löffler, Martin Nöllenburg and Rodrigo Silveira. Adjacency-Preserving Spatial Treemaps
  • Pooya Davoodi, Gerth Stølting 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