18. ESA 2010: Liverpool, UK

Invited Talk

• Paul Bendich, Herbert Edelsbrunner, Dmitriy Morozov, Amit K. Patel:
  The Robustness of Level Sets. 1-10
  

Session 1a

• Friedrich Eisenbrand, Karthikeyan Kesavan, Raju S. Mattikalli, Martin Niemeier, Arnold W. Nordsieck, Martin Skutella, José Verschae, Andreas Wiese:
  Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods. 11-22
  
• Sze-Hang Chan, Tak Wah Lam, Lap-Kei Lee:
  Non-clairvoyant Speed Scaling for Weighted Flow Time. 23-35
  
• Martin Skutella, José Verschae:
  A Robust PTAS for Machine Covering and Packing. 36-47
  

Session 1b

• Shay Solomon, Michael Elkin:
  Balancing Degree, Diameter and Weight in Euclidean Spanners. 48-59
  
• Frank Hellweg, Melanie Schmidt, Christian Sohler:
  Testing Euclidean Spanners. 60-71
  
• Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski:
  Fast Approximation in Subspaces by Doubling Metric Decomposition. 72-83
  
• Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty:
  f-Sensitivity Distance Oracles and Routing Schemes. 84-96
  

Session 2a

• Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos:
  Fast Minor Testing in Planar Graphs. 97-109
  
• Kevin Buchin, André Schulz:
  On the Number of Spanning Trees a Planar Graph Can Have. 110-121
  
• Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos:
  Contractions of Planar Graphs in Polynomial Time. 122-133
  

Session 2b

• Petra Berenbrink, Robert Elsässer, Thomas Sauerwald:
  Communication Complexity of Quasirandom Rumor Spreading. 134-145
  
• Emmanouil Pountourakis, Angelina Vidali:
  A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing. 146-157
  
• Elliot Anshelevich, Martin Hoefer:
  Contribution Games in Social Networks. 158-169
  

Session 3a

• Bahman Bahmani, Michael Kapralov:
  Improved Bounds for Online Stochastic Matching. 170-181
  
• Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, Clifford Stein:
  Online Stochastic Packing Applied to Display Ad Allocation. 182-194
  
• Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, Haifeng Xu:
  Caching Is Hard - Even in the Fault Model. 195-206
  

Session 3b

• Ferdinando Cicalese, Ugo Vaccaro:
  Superselectors: Efficient Constructions and Applications. 207-218
  
• Abhimanyu Das, David Kempe:
  Estimating the Average of a Lipschitz-Continuous Function from One Sample. 219-230
  
• Graham Cormode, Michael Mitzenmacher, Justin Thaler:
  Streaming Graph Computations with a Helpful Advisor. 231-242
  

Session 4a

• Matt Gibson, Imran A. Pirwani:
  Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier - (Extended Abstract). 243-254
  
• Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz:
  Minimum Vertex Cover in Rectangle Graphs. 255-266
  
• Serge Gaspers, Matthias Mnich:
  Feedback Vertex Sets in Tournaments. 267-277
  

Session 4b

• Vitaly Osipov, Peter Sanders:
  n-Level Graph Partitioning. 278-289
  
• Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, Fabien Viger:
  Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns. 290-301
  
• Pierluigi Crescenzi, Roberto Grossi, Claudio Imbrenda, Leonardo Lanzi, Andrea Marino:
  Finding the Diameter in Real-World Graphs - Experimentally Turning a Lower Bound into an Upper Bound. 302-313
  

Session 5a

• MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz:
  Budgeted Red-Blue Median and Its Generalizations. 314-325
  
• Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo:
  All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables. 326-337
  
• Laura Galli, Sebastian Stiller:
  Strong Formulations for the Multi-module PESP and a Quadratic Algorithm for Graphical Diophantine Equation Systems. 338-349
  
• Christina Büsing, Jens Maue:
  Robust Algorithms for Sorting Railway Cars. 350-361
  

Session 5b

• Matthew T. Dickerson, David Eppstein, Michael T. Goodrich:
  Cloning Voronoi Diagrams via Retroactive Data Structures. 362-373
  
• Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
  A Unified Approach to Approximate Proximity Searching. 374-385
  
• Sorelle A. Friedler, David M. Mount:
  Spatio-temporal Range Searching over Compressed Kinetic Sensor Data. 386-397
  
• Michael Hemmer, Ophir Setter, Dan Halperin:
  Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space - with Fast Point-Location. 398-409
  

Invited Talk

• Artur Czumaj:
  Local Graph Exploration and Fast Property Testing. 410-414
  

Session 6a

• Kuan-Yu Chen, Kun-Mao Chao:
  A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings. 415-426
  
• Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna:
  Fast Prefix Search in Little Space, with Applications. 427-438
  
• Hiroshi Fujiwara, Tobias Jacobs:
  On the Huffman and Alphabetic Tree Problem with General Cost Functions. 439-450
  
• Juha Kärkkäinen, Simon J. Puglisi:
  Medium-Space Algorithms for Inverse BWT. 451-462
  

Session 6b

• Kevin Buchin, Maike Buchin, Marc J. van Kreveld, Maarten Löffler, Rodrigo I. Silveira, Carola Wenk, Lionov Wiratma:
  Median Trajectories. 463-474
  
• Haim Kaplan, Matthew J. Katz, Gila Morgenstern, Micha Sharir:
  Optimal Cover of Points by Disks in a Simple Polygon. 475-486
  
• Pankaj K. Agarwal, Jeff M. Phillips, Hai Yu:
  Stability of epsilon-Kernels. 487-499
  
• Sang Won Bae, Matias Korman, Yoshio Okamoto:
  The Geodesic Diameter of Polygonal Domains. 500-511
  

Session 7a

• Ulf Lorenz, Alexander Martin, Jan Wolf:
  Polyhedral and Algorithmic Properties of Quantified Linear Programs. 512-523
  
• Joachim Giesen, Martin Jaggi, Sören Laue:
  Approximating Parameterized Convex Optimization Problems. 524-535
  
• Fabrizio Grandoni, Rico Zenklusen:
  Approximation Schemes for Multi-Budgeted Independence Systems. 536-548
  

Session 7b

• Michael Lampis:
  Algorithmic Meta-theorems for Restrictions of Treewidth. 549-560
  
• Viresh Patel:
  Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus. 561-572
  
• Jesper Jansson, Wing-Kin Sung:
  Constructing the R* Consensus Tree of Two Trees in Subcubic Time. 573-584
  

Last update Thu May 24 04:17:16 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page