Algorithms - ESA 2010 : 18th annual European symposium, Liverpool, UK, September 6-8, 2010 : proceedings / Part I

Annotation This book constitutes the proceedings of the 18th Annual European Symposium on Algorithms, held in Liverpool, UK in September 2010 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 -