Pub. Date:
Algorithms - ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010, Proceedings

Algorithms - ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010, Proceedings


View All Available Formats & Editions
Choose Expedited Shipping at checkout for delivery by Tuesday, October 26


This book constitutes the proceedings of the 18th Annual European Symposium on Algorithms, held in Liverpool, UK in September 2010.

Related collections and offers

Product Details

ISBN-13: 9783642157745
Publisher: Springer Berlin Heidelberg
Publication date: 11/04/2010
Series: Lecture Notes in Computer Science , #6346
Edition description: 2010
Pages: 587
Product dimensions: 6.10(w) x 9.20(h) x 1.20(d)

Table of Contents

Invited Talk

The Robustness of Level Sets Paul Bendich Herbert Edelsbrunner Dmitriy Morozov Amit Patel 1

Session 1a

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods Friedrich Eisenbrand Karthikeyan Kesavan Raju S. Mattikalli Martin Niemeier Arnold W. Nordsieck Martin Skutella José Verschae Andreas Wiese 11

Non-clairvoyant Speed Scaling for Weighted Flow Time Sze-Hang Chan Tak- Wah Lam Lap-Kei Lee 23

A Robust PTAS for Machine Covering and Packing Martin Skutella José Verschae 36

Session 1b

Balancing Degree, Diameter and Weight in Euclidean Spanners Shay Solomon Michael Elkin 48

Testing Euclidean Spanners Frank Hellweg Melanie Schmidt Christian Sohler 60

Fast Approximation in Subspaces by Doubling Metric Decomposition Marek Cygan Lukasz Kowalik Marcin Mucha Marcin Pilipczuk Piotr Sankowski 72

f-Sensitivity Distance Oracles and Routing Schemes Shiri Chechik Michael Langberg David Peleg Liam Roditty 84

Session 2a

Fast Minor Testing in Planar Graphs Isolde Adler Frederic Dorn Fedor V. Fomin Ignasi Sau Dimitrios M. Thilikos 97

On the Number of Spanning Trees a Planar Graph Can Have Kevin Buchin André Schulz 110

Contractions of Planar Graphs in Polynomial Time Marcin Kaminski Daniël Paulusma Dimitrios M. Thilikos 122

Session 2b

Communication Complexity of Quasirandom Rumor Spreading Petra Berenbrink Robert Elsässer Thomas Sauerwald 134

A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing Emmanouil Pountourakis Angelina Vidali 146

Contribution Games in Social Networks Elliot Anshelevich Martin Hoefer 158

Session 3a

Improved Bounds for Online Stochastic Matching Bahman Bahmani Michael Kapralov 170

Online Stochastic Packing Applied to Display Ad Allocation Jon Feldman Monika Henzinger Nitish Korula Vahab S. Mirrokni Cliff Stein 182

Caching Is Hard - Even in the Fault Model Marek Chrobak Gerhard J. Woeginger Kazuhisa Makino Haifeng Xu 195

Session 3b

Superselectors: Efficient Constructions and Applications Ferdinando Cicalese Ugo Vaccaro 207

Estimating the Average of a Lipschitz-Continuous Function from One Sample Abhimanyu Das David Kempe 219

Streaming Graph Computations with a Helpful Advisor Graham Cormode Michael Mitzenmacher Justin Thaler 231

Session 4a

Algorithms for Dominating Set in Disk Graphs: Breaking the log n Barrier Matt Gibson Imran A. Pirwani 243

Minimum Vertex Cover in Rectangle Graphs Reuven Bar- Yehuda Danny Hermelin Dror Rawitz 255

Feedback Vertex Sets in Tournaments Serge Gaspers Matthias Mnich 267

Session 4b

n-Level Graph Partitioning Vitaly Osipov Peter Sanders 278

Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns Hannah Bast Erik Carlsson Arno Eigenwillig Robert Geisberger Chris Harrelson Veselin Raychev Fabien Viger 290

Finding the Diameter in Real-World Graphs: Experimentally Turning a Lower Bound into an Upper Bound Pierluigi Crescenzi Roberto Grossi Claudio Imbrenda Leonardo Lanzi Andrea Marino 302

Session 5a

Budgeted Red-Blue Median and Its Generalizations MohammadTaghi Hajiaghayi Rohit Khandekar Guy Kortsarz 314

All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables Gregory Gutin Leo van Iersel Matthias Mnich Anders Yeo 326

Strong Formulations for the Multi-module PESP and a Quadratic Algorithm for Graphical Diophantine Equation Systems Laura Galli Sebastian Stiller 338

Robust Algorithms for Sorting Railway Cars Christina Büsing Jens Maue 350

Session 5b

Cloning Voronoi Diagrams via Retroactive Data Structures Matthew T. Dickerson David Eppstein Michael T. Goodrich 362

A Unified Approach to Approximate Proximity Searching Sunil Arya Guilherme D. da Fonseca David M. Mount 374

Spatio-temporal Range Searching over Compressed Kinetic Data Sorelle A. Friedler David M. Mount 386

Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space: with Fast Point-Location Michael Hemmer Ophir Setter Dan Halperin 398

Invited Talk

Local Graph Exploration and Fast Property Testing Artur Czumaj 410

Session 6a

A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings Kuan-Yu Chen Kun-Mao Chao 415

Fast Prefix Search in Little Space, with Applications Djamal Belazzougui Paolo Boldi Rasmus Pagh Sebastiano Vigna 427

On the Huffman and Alphabetic Tree Problem with General Cost Functions Hiroshi Fujiwara Tobias Jacobs 439

Medium-Space Algorithms for Inverse BWT Juha Kärkkäinen Simon J. Puglisi 451

Session 6b

Median Trajectories Kevin Buchin Maike Buchin Marc van Kreveld Maarten Löffler Rodrigo I. Silveira Carola Wenk Lionov Wiratma 463

Optimal Cover of Points by Disks in a Simple Polygon Haim Kaplan Matthew J. Katz Gila Morgenstern Micha Sharir 475

Stability of ε-Kernels Pankaj K. Agarwal Jeff M. Phillips Hai Yu 487

The Geodesic Diameter of Polygonal Domains Sang Won Bae Matias Korman Yoshio Okamoto 500

Session 7a

Polyhedral and Algorithmic Properties of Quantified Linear Programs Ulf Lorenz Alexander Martin Jan Wolf 512

Approximating Parameterized Convex Optimization Problems Joachim Giesen Martin Jaggi Sören Laue 524

Approximation Schemes for Multi-Budgeted Independence Systems Fabrizio Grandoni Rico Zenklusen 536

Session 7b

Algorithmic Meta-theorems for Restrictions of Treewidth Michael Lampis 549

Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus Viresh Patel 561

Constructing the R* Consensus Tree of Two Trees in Subcubic Time Jesper Jansson Wing-Kin Sung 573

Author Index 585

Customer Reviews