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”