18th Annual European Symposium on Algorithms

6th - 8th September 2010
University of Liverpool, United Kingdom

Accepted Papers

  1. Ittai Abraham, Yair Bartal, Ofer Neiman and Leonard Schulman. “Volume in General Metric Spaces
  2. Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau and Dimitrios Thilikos. “Fast Minor Testing in Planar Graphs
  3. Pankaj Agarwal, Jeff Phillips and Hai Yu. “Stability of eps-Kernels
  4. Deepak Ajwani, Nodari Sitchinava and Norbert Zeh. “Geometric Algorithms for Private-Cache Chip Multiprocessors
  5. Elliot Anshelevich and Martin Hoefer. “Contribution Games in Social Networks
  6. Sunil Arya, Guilherme da Fonseca and David Mount. “A Unified Approach to Approximate Proximity Searching
  7. Yossi Azar, Niv Buchbinder and Kamal Jain. “How to Allocate Goods in an Online Market?
  8. Sang Won Bae, Matias Korman and Yoshio Okamoto. “The Geodesic Diameter of Polygonal Domains
  9. Bahman Bahmani and Michael Kapralov. “Improved Bounds for Online Stochastic Matching
  10. Nikhil Bansal, Anupam Gupta, Jian Li, Julian Mestre, Viswanath Nagarajan and Atri Rudra. “When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
  11. Reuven Bar-Yehuda, Danny Hermelin and Dror Rawitz. “Minimum Vertex Cover in Rectangle Graphs
  12. Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev and Fabien Viger. “Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
  13. Djamal Belazzougui, Paolo Boldi, Rasmus Pagh and Sebastiano Vigna. “Fast Prefix Search in Little Space
  14. Petra Berenbrink, Robert Elsässer and Thomas Sauerwald. “Communication Complexity of Quasirandom Rumor Spreading
  15. Kshipra Bhawalkar, Martin Gairing and Tim Roughgarden. “Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, Tightness
  16. Vincenzo Bonifaci and Alberto Marchetti-Spaccamela. “Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
  17. Gerth Stølting Brodal, Pooya Davoodi and S. Srinivasa Rao. “On Space Efficient Two Dimensional Range Minimum Data Structures
  18. Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Löffler, Rodrigo Silveira, Carola Wenk and Lionov Wiratma. “Median Trajectories
  19. Kevin Buchin, Maike Buchin and André Schulz. “Frechet Distance of Surfaces: Some Simple Hard Cases
  20. Kevin Buchin and André Schulz. “On the Number of Spanning Trees a Planar Graph Can Have
  21. Christina Büsing and Jens Maue. “Robust Algorithms for Sorting Railway Cars
  22. Sze-Hang Chan, Tak-Wah Lam and Lap-Kei Lee. “Non-clairvoyant Speed Scaling for Weighted Flow Time
  23. Shiri Chechik, Michael Langberg, Liam Roditty and David Peleg. “$f$-Sensitivity Distance Oracles and Routing Schemes
  24. Kuan-Yu Chen and Kun-Mao Chao. “A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings
  25. Ning Chen and Arpita Ghosh. “Strongly Stable Assignment
  26. Marek Chrobak, Gerhard Woeginger, Kazuhisa Makino and Haifeng Xu. “Caching is Hard – Even in the Fault Model
  27. Ferdinando Cicalese and Ugo Vaccaro. “Superselectors: Efficient Constructions and Applications
  28. Pierluigi Crescenzi, Roberto Grossi, Claudio Imbrenda, Leonardo Lanzi and Andrea Marino. “Finding the Diameter in Large Graphs: Experimentally turning a lower bound into an upper bound
  29. Shane Culpepper, Gonzalo Navarro, Simon Puglisi and Andrew Turpin. “Top-k Ranked Document Search in General Text Databases
  30. Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk and Piotr Sankowski. “Fast Approximation in Subspaces by Doubling Metric Decomposition
  31. Abhimanyu Das and David Kempe. “Estimating the Average of a Lipschitz-Continuous Function from One Sample
  32. Matthew Dickerson, David Eppstein and Michael Goodrich. “Cloning Voronoi Diagrams via Retroactive Data Structures
  33. Friedrich Eisenbrand, Karthikeyan Kesavan, Raju Mattikalli, Martin Niemeier, Arnold Nordsieck, Martin Skutella, Jose Verschae and Andreas Wiese. “Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods
  34. Amr Elmasry. “Pairing Heaps with Costless Meld
  35. Jon Feldman, Monika Henzinger, Nitish Korula, Vahab Mirrokni and Cliff Stein. “Online Stochastic Packing applied to Display Ad Allocation
  36. Sorelle Friedler and David Mount. “Spatio-temporal Range Searching Over Compressed Kinetic Sensor Data
  37. Hiroshi Fujiwara and Tobias Jacobs. “On the Huffman and Alphabetic Tree Problem with General Cost Functions
  38. Laura Galli and Sebastian Stiller. “Strong formulations for the Multi-module PESP and a quadratic algorithm for Graphical Diophantine Equation Systems
  39. Serge Gaspers and Matthias Mnich. “Feedback Vertex Sets in Tournaments
  40. Matt Gibson and Imran Pirwani. “Approximation Algorithms for Dominating Set in Disk Graphs
  41. Joachim Giesen, Martin Jaggi and Soeren Laue. “Approximating Parameterized Convex Optimization Problems
  42. Fabrizio Grandoni and Rico Zenklusen. “Optimization with More than One Budget
  43. Gregory Gutin, Leo van Iersel, Matthias Mnich and Anders Yeo. “All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Polynomial Kernels
  44. MohammadTaghi Hajiaghayi, Rohit Khandekar and Guy Kortsarz. “Budgeted Red-Blue Median and its Generalizations
  45. Tobias Harks, Martin Hoefer, Max Klimm and Alexander Skopalik. “Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games
  46. Frank Hellweg, Melanie Schmidt and Christian Sohler. “Testing Euclidean Spanners
  47. Michael Hemmer, Ophir Setter and Dan Halperin. “Constructing the Exact Voronoi Diagram of Arbitrary Lines in Space with Fast Point-Location
  48. Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa. “A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
  49. Jesper Jansson and Wing-Kin Sung. “Constructing the R* consensus tree of two trees in subcubic time
  50. Marcin Kaminski, Daniel Paulusma and Dimitrios Thilikos. “Contractions of planar graphs in polynomial time
  51. Ross Kang, Matthias Mnich and Tobias Müller. “Induced matchings in subcubic planar graphs
  52. Haim Kaplan, Matthew J. Katz, Gila Morgenstern and Micha Sharir. “Optimal cover of points by disks in a simple polygon
  53. Yusuke Kobayashi, Ryo Fujita and Kazuhisa Makino. “Robust Matchings and Matroid Intersections
  54. Piotr Krysta and Carmine Ventre. “Combinatorial Auctions with Verification are Tractable
  55. Juha Kärkkäinen and Simon Puglisi. “Medium-Space Algorithms for Inverse BWT
  56. Michael Lampis. “Algorithmic Meta-theorems for Restrictions of Treewidth
  57. Ulf Lorenz, Alexander Martin and Jan Wolf. “Polyhedral and algorithmic Properties of Quantified Linear Programs
  58. Shay Mozes and Christian Wulff-Nilsen. “Shortest Paths in Planar Graphs with Real Lengths in O(n log2(n) / loglog n) Time
  59. Vitaly Osipov and Peter Sanders. “n-Level Graph Partitioning
  60. Viresh Patel. “Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
  61. Emmanouil Pountourakis and Angelina Vidali. “A complete characterization of group-strategyproof mechanisms of cost-sharing
  62. Jaikumar Radhakrishnan, Smit Shah and Saswata Shannigrahi. “Data Structures for Storing Small Sets in the Bitprobe Model
  63. Martin Skutella and Jose Verschae. “A Robust PTAS for Machine Covering and Packing
  64. Shay Solomon and Michael Elkin. “Balancing Degree, Diameter and Weight in Euclidean Spanners
  65. Justin Thaler, Graham Cormode and Michael Mitzenmacher. “Streaming Graph Computations with a Helpful Advisor
  66. Éric Colin de Verdière. “Shortest Cut Graph of a Surface with Prescribed Vertex Set