21st European Symposium on Algorithms
ESA 2013
September 02-04
Sophia Antipolis, France



Design and Analysis track

Paolo Ferragina and Rossano Venturini. Compressed Cache-Oblivious String B-tree
Marek Cygan, Fabrizio Grandoni and Danny Hermelin. Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
Stefan Kratsch. On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
Elliot Anshelevich, Onkar Bhardwaj and Martin Hoefer. Friendship and Stable Matching
Fedor Fomin and Michał Pilipczuk. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
Joachim Gudmundsson and Michiel Smid. Frechet queries in geometric trees
Wolfgang Dvořák, Monika Henzinger and David Williamson. Maximizing a Submodular Function with a Non-Downward Closed Constraint
Thomas Kesselheim, Klaus Radke, Andreas Tönnis and Berthold Vöcking . An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
Travis Gagie, Danny Hermelin, Gad M. Landau and Oren Weimann. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
Michael Crouch, Andrew McGregor and Daniel Stubbs. Dynamic Graphs in the Sliding-Window Model
Subhash Suri, Kevin Verbeek and Hakan Yıldız. On the Most Likely Convex Hull of Uncertain Points
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna and Giuseppe Persiano. Logit Dynamics with Concurrent Updates for Local Interaction Games
Panos Giannopoulos, Christian Knauer and Daniel Werner. On the computational complexity of Erd\H os-Szekeres and related problems in $\R^3$
Shiri Chechik, Matthew Johnson, Merav Parter and David Peleg. Secluded Connectivity Problems
Michael Fellows, Danny Hermelin, Frances A. Rosamond and Hadas Shachnai. Tractable Parameterizations for the Minimum Linear Arrangement Problem
Rajesh Chitnis, Laszlo Egri and Daniel Marx. List H-Coloring a Graph by Removing Few Vertices
Fedor Fomin and Petr Golovach. Long Circuits and Large Euler Subgraphs
Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen and Veli Mäkinen. Versatile succinct representations of the bidirectional Burrows-Wheeler transform
Sharma V. Thankachan, Rahul Shah, Cheng Sheng and Jeff Vitter. Top-k Document Retrieval in External Memory
Lucas Bueno and Jorge Stolfi. Economic 3-Colored Subdivision of Triangulations
Oswin Aichholzer, Wolfgang Mulzer and Alexander Pilz. Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
Hu Ding and Jinhui Xu. PTAS for Minimizing Earth Mover's Distance under Rigid Transformations
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter. Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
Ramanujan M. S., Saket Saurabh, Daniel Lokshtanov, Ondrej Suchy and Mark Jones. Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Andrea Clementi, Pierluigi Crescenzi, Carola Doerr, Pierre Fraigniaud, Marco Isopi, Alessandro Panconesi, Francesco Pasquale and Riccardo Silvestri. Rumor Spreading in Random Evolving Graphs
Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe Francesco Italiano and Andrea Ribichini. On Resilient Graph Spanners
Megha Khosla. Balls into Bins made Faster
Kim Thang Nguyen. Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling
Ioannis Caragiannis, Christos Kaklamanis and Maria Kyropoulou. Limitations of deterministic auction design for correlated bidders
Ivan Bliznets, Fedor Fomin, Michał Pilipczuk and Yngve Villanger. Largest chordal and interval subgraphs faster than 2^n
Kevin Buchin, Maike Buchin, Rolf van Leusden, Wouter Meulemans and Wolfgang Mulzer. Computing the Fréchet Distance with a Retractable Leash
David Adjiashvili, Gianpaolo Oriolo and Marco Senatore. The Online Replacement Path Problem
Lelia Blin, Janna Burman and Nicolas Nisse. Exclusive Graph Searching
Linda Farczadi, Jochen Koenemann and Konstantinos Georgiou. Network bargaining with general capacities
Martin Nöllenburg and Roman Prutkin. Euclidean Greedy Drawings of Trees
Merav Parter and David Peleg. Sparse Fault-Tolerant BFS Trees
Jochen Konemann, Sina Sadeghian and Laura Sanita. Better Approximation Algorithms for Technology Diffusion
Davide Bilò, Luciano Gualà and Guido Proietti. A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree
Prosenjit Bose, Jean-Lou De Carufel and Stephane Durocher. Revisiting the Problem of Searching on a Line
Jop Briet, Daniel Dadush and Sebastian Pokutta. On the existence of 0/1 polytopes with high semidefinite extension complexity
George Mertzios. The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
Bart De Keijzer, Evangelos Markakis, Guido Schaefer and Orestis Telelis. Inefficiency of Standard Multi-Unit Auctions
Nadia Fawaz, S Muthukrishnan and Aleksandar Nikolov. Nearly Optimal Private Convolution
Christoph Berkholz, Paul Bonsma and Martin Grohe. Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Radu Curticapean and Marvin Künnemann. A Quantization Framework for Smoothed Analysis on Euclidean Optimization Problems
Amotz Bar-Noy, Dror Rawitz and Peter Terlecky. Maximizing Barrier Coverage Lifetime with Mobile Sensors
Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman and Srinivasa Rao Satti. Encodings for Range Selection and Top-k Queries
Yakov Nekrich and Jeffrey Scott Vitter. Optimal Color Range Reporting in One Dimension
Jannik Matuschke, Andreas Bley and Benjamin Müller. Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections
Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez and Somnath Sikdar. Kernelization Using Structural Parameters on Sparse Graph Classes
Gerth Stølting Brodal, Pooya Davoodi and Andrej Brodnik. The Encoding Complexity of Two Dimensional Range Minimum Data Structures
Pasin Manurangsi and Dana Moshkovitz. Improved Approximation Algorithms for Projection Games

Engineering and Applications track

Moritz Kobitzsch. An Alternative Approach to Alternative Routes: HiDAR
Kevin Buchin, Olivier Devillers, Wolfgang Mulzer, Okke Schrijvers and Jonathan Shewchuk. Vertex Deletion for 3D Delaunay Triangulations
Frederic Cazals, Deepesh Agarwal, Julio-Cesar Silva Araujo, Christelle Caillouet, David Coudert and Stephane Perennes. Connectivity Inference in Mass Spectrometry based Structure Determination
Nir Halman, Giacomo Nannicini and James Orlin. A Practical FPTAS for Convex Stochastic Dynamic Programs
Sander P. A. Alewijnse, Quirijn W. Bouts, Alex P. ten Brink and Kevin Buchin. Computing the Greedy Spanner in Linear Space
Andreas Beckmann, Ulrich Meyer and David Veith. An Implementation of I/O-efficient Dynamic Breadth-First Search using level-aligned hierarchical Clustering
Lars Arge, Gerth Stølting Brodal, Jakob Truelsen and Constantinos Tsirogiannis. An optimal and practical cache-oblivious algorithm for computing multiresolution rasters
Kai Xiao, Danny Z. Chen, X. Sharon Hu and Bo Zhou. Shell: A Spatial Decomposition Data Structure for 3D Curve Traversal on Many-core Architectures
Timo Bingmann and Peter Sanders. Parallel String Sample Sort
Hendrik Fichtenberger, Marc Gillé, Melanie Schmidt, Chris Schwiegelshohn and Christian Sohler. BICO: BIRCH meets Coresets for k-means
Clément Maria, Jean-Daniel Boissonnat and Tamal Dey. The Compressed Annotation Matrix: an Efficient Data Structure for Computing Persistent Cohomology
Jeremy Barbay, Ankur Gupta, Seungbum Jo, Srinivasa Rao Satti and Jonathan Sorenson. Theory and Implementation of Online Multiselection Algorithms
Deepak Ajwani and Nodari Sitchinava. Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures
Shin-Ichi Minato. Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets
Mark De Berg and Dirk H.P. Gerrits. Labeling Moving Points with a Trade-Off Between Label Speed and Label Overlap
Sándor Laki and Tamás Lukovszki. Balanced Neighbor Selection for BitTorrent-like Networks


logo Inria logo U-Nice   logo I3S   logo I3S                     logo EATCS    logo eurecom    logo paca                   logo Google       
webmaster - credits