Algorithms – ESA 2013

1. Front Matter

   PDF

2. The Online Replacement Path Problem

   • David Adjiashvili, Gianpaolo Oriolo, Marco Senatore

   Pages 1-12

3. Flip Distance between Triangulations of a Simple Polygon is NP-Complete

   • Oswin Aichholzer, Wolfgang Mulzer, Alexander Pilz

   Pages 13-24

4. Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures

   • Deepak Ajwani, Nodari Sitchinava

   Pages 25-36

5. Computing the Greedy Spanner in Linear Space

   • Sander P. A. Alewijnse, Quirijn W. Bouts, Alex P. ten Brink, Kevin Buchin

   Pages 37-48

6. Friendship and Stable Matching

   • Elliot Anshelevich, Onkar Bhardwaj, Martin Hoefer

   Pages 49-60

7. An Optimal and Practical Cache-Oblivious Algorithm for Computing Multiresolution Rasters

   • Lars Arge, Gerth Stølting Brodal, Jakob Truelsen, Constantinos Tsirogiannis

   Pages 61-72

8. Logit Dynamics with Concurrent Updates for Local Interaction Games

   • Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna, Giuseppe Persiano

   Pages 73-84

9. On Resilient Graph Spanners

   • Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe Francesco Italiano, Andrea Ribichini

   Pages 85-96

10. Maximizing Barrier Coverage Lifetime with Mobile Sensors

    • Amotz Bar-Noy, Dror Rawitz, Peter Terlecky

    Pages 97-108

11. Theory and Implementation of Online Multiselection Algorithms

    • Jérémy Barbay, Ankur Gupta, Seungbum Jo, Satti Srinivasa Rao, Jonathan Sorenson

    Pages 109-120

12. An Implementation of I/O-Efficient Dynamic Breadth-First Search Using Level-Aligned Hierarchical Clustering

    • Andreas Beckmann, Ulrich Meyer, David Veith

    Pages 121-132

13. Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform

    • Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, Veli Mäkinen

    Pages 133-144

14. Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

    • Christoph Berkholz, Paul Bonsma, Martin Grohe

    Pages 145-156

15. A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree

    • Davide Bilò, Luciano Gualà, Guido Proietti

    Pages 157-168

16. Parallel String Sample Sort

    • Timo Bingmann, Peter Sanders

    Pages 169-180

17. Exclusive Graph Searching

    • Lélia Blin, Janna Burman, Nicolas Nisse

    Pages 181-192

18. Largest Chordal and Interval Subgraphs Faster Than 2ⁿ

    • Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger

    Pages 193-204

19. Revisiting the Problem of Searching on a Line

    • Prosenjit Bose, Jean-Lou De Carufel, Stephane Durocher

    Pages 205-216

20. On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity

    • Jop Briët, Daniel Dadush, Sebastian Pokutta

    Pages 217-228

This book constitutes the refereed proceedings of the 21st Annual European Symposium on Algorithms, ESA 2013, held in Sophia Antipolis, France, in September 2013 in the context of the combined conference ALGO 2013. The 69 revised full papers presented were carefully reviewed and selected from 303 initial submissions: 53 out of 229 in track "Design and Analysis" and 16 out of 74 in track "Engineering and Applications". The papers in this book present original research in all areas of algorithmic research, including but not limited to: algorithm engineering; algorithmic aspects of networks; algorithmic game theory; approximation algorithms; computational biology; computational finance; computational geometry; combinatorial optimization; data compression; data structures; databases and information retrieval; distributed and parallel computing; graph algorithms; hierarchical memories; heuristics and meta-heuristics; mathematical programming; mobile computing; on-line algorithms; parameterized complexity; pattern matching; quantum computing; randomized algorithms; scheduling and resource allocation problems; streaming algorithms.

• experimental algorithms
• mobile computing
• online algorithms
• parallel string sorting
• technology diffusion
• algorithm analysis and problem complexity
• data structures

• Department of Computer Science, Utrecht University, Utrecht, The Netherlands

  Hans L. Bodlaender

• Dipartimento di Ingegneria Civile e Ingegneria Informatica, Università di Roma “Tor Vergata”, Rome, Italy

  Giuseppe F. Italiano

Policies and ethics