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

Front Matter....Pages -
The Robustness of Level Sets....Pages 1-10
Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods....Pages 11-22
Non-clairvoyant Speed Scaling for Weighted Flow Time....Pages 23-35
A Robust PTAS for Machine Covering and Packing....Pages 36-47
Balancing Degree, Diameter and Weight in Euclidean Spanners....Pages 48-59
Testing Euclidean Spanners....Pages 60-71
Fast Approximation in Subspaces by Doubling Metric Decomposition....Pages 72-83
 f -Sensitivity Distance Oracles and Routing Schemes....Pages 84-96
Fast Minor Testing in Planar Graphs....Pages 97-109
On the Number of Spanning Trees a Planar Graph Can Have....Pages 110-121
Contractions of Planar Graphs in Polynomial Time....Pages 122-133
Communication Complexity of Quasirandom Rumor Spreading....Pages 134-145
A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing....Pages 146-157
Contribution Games in Social Networks....Pages 158-169
Improved Bounds for Online Stochastic Matching....Pages 170-181
Online Stochastic Packing Applied to Display Ad Allocation....Pages 182-194
Caching Is Hard – Even in the Fault Model....Pages 195-206
Superselectors: Efficient Constructions and Applications....Pages 207-218
Estimating the Average of a Lipschitz-Continuous Function from One Sample....Pages 219-230
Streaming Graph Computations with a Helpful Advisor....Pages 231-242
Algorithms for Dominating Set in Disk Graphs: Breaking the log n Barrier....Pages 243-254
Minimum Vertex Cover in Rectangle Graphs....Pages 255-266
Feedback Vertex Sets in Tournaments....Pages 267-277
 n -Level Graph Partitioning....Pages 278-289
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns....Pages 290-301
Finding the Diameter in Real-World Graphs....Pages 302-313
Budgeted Red-Blue Median and Its Generalizations....Pages 314-325
All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables....Pages 326-337
Strong Formulations for the Multi-module PESP and a Quadratic Algorithm for Graphical Diophantine Equation Systems....Pages 338-349
Robust Algorithms for Sorting Railway Cars....Pages 350-361
Cloning Voronoi Diagrams via Retroactive Data Structures....Pages 362-373
A Unified Approach to Approximate Proximity Searching....Pages 374-385
Spatio-temporal Range Searching over Compressed Kinetic Sensor Data....Pages 386-397
Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space....Pages 398-409
Local Graph Exploration and Fast Property Testing....Pages 410-414
A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings....Pages 415-426
Fast Prefix Search in Little Space, with Applications....Pages 427-438
On the Huffman and Alphabetic Tree Problem with General Cost Functions....Pages 439-450
Medium-Space Algorithms for Inverse BWT....Pages 451-462
Median Trajectories....Pages 463-474
Optimal Cover of Points by Disks in a Simple Polygon....Pages 475-486
Stability of ε -Kernels....Pages 487-499
The Geodesic Diameter of Polygonal Domains....Pages 500-511
Polyhedral and Algorithmic Properties of Quantified Linear Programs....Pages 512-523
Approximating Parameterized Convex Optimization Problems....Pages 524-535
Approximation Schemes for Multi-Budgeted Independence Systems....Pages 536-548
Algorithmic Meta-theorems for Restrictions of Treewidth....Pages 549-560
Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus....Pages 561-572
Constructing the R* Consensus Tree of Two Trees in Subcubic Time....Pages 573-584
Back Matter....Pages -