LEADER 07288nam 22008655 450 001 9910484493003321 005 20251226195743.0 010 $a1-280-38904-4 010 $a9786613566966 010 $a3-642-15775-0 024 7 $a10.1007/978-3-642-15775-2 035 $a(CKB)2670000000045103 035 $a(SSID)ssj0000446289 035 $a(PQKBManifestationID)11315790 035 $a(PQKBTitleCode)TC0000446289 035 $a(PQKBWorkID)10491044 035 $a(PQKB)11189525 035 $a(DE-He213)978-3-642-15775-2 035 $a(MiAaPQ)EBC3065746 035 $a(PPN)149024460 035 $a(BIP)32107223 035 $a(EXLCZ)992670000000045103 100 $a20100901d2010 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithms - ESA 2010 $e18th Annual European Symposium, Liverpool, UK, September 6-8, 2010, Proceedings /$fedited by Mark de Berg, Ulrich Meyer 205 $a1st ed. 2010. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2010. 215 $a1 online resource (XVIII, 587 p. 68 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v6346 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-642-15774-2 320 $aIncludes bibliographical references and index. 327 $aInvited Talk -- The Robustness of Level Sets -- Session 1a -- Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods -- Non-clairvoyant Speed Scaling for Weighted Flow Time -- A Robust PTAS for Machine Covering and Packing -- Session 1b -- Balancing Degree, Diameter and Weight in Euclidean Spanners -- Testing Euclidean Spanners -- Fast Approximation in Subspaces by Doubling Metric Decomposition -- f-Sensitivity Distance Oracles and Routing Schemes -- Session 2a -- Fast Minor Testing in Planar Graphs -- On the Number of Spanning Trees a Planar Graph Can Have -- Contractions of Planar Graphs in Polynomial Time -- Session 2b -- Communication Complexity of Quasirandom Rumor Spreading -- A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing -- Contribution Games in Social Networks -- Session 3a -- Improved Bounds for Online Stochastic Matching -- Online Stochastic Packing Applied to Display Ad Allocation -- Caching Is Hard ? Even in the Fault Model -- Session 3b -- Superselectors: Efficient Constructions and Applications -- Estimating the Average of a Lipschitz-Continuous Function from One Sample -- Streaming Graph Computations with a Helpful Advisor -- Session 4a -- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier -- Minimum Vertex Cover in Rectangle Graphs -- Feedback Vertex Sets in Tournaments -- Session 4b -- n-Level Graph Partitioning -- Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns -- Finding the Diameter in Real-World Graphs -- Session 5a -- Budgeted Red-Blue Median and Its Generalizations -- All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables -- Strong Formulations for the Multi-module PESP and a Quadratic Algorithm forGraphical Diophantine Equation Systems -- Robust Algorithms for Sorting Railway Cars -- Session 5b -- Cloning Voronoi Diagrams via Retroactive Data Structures -- A Unified Approach to Approximate Proximity Searching -- Spatio-temporal Range Searching over Compressed Kinetic Sensor Data -- Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space -- Invited Talk -- Local Graph Exploration and Fast Property Testing -- Session 6a -- A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings -- Fast Prefix Search in Little Space, with Applications -- On the Huffman and Alphabetic Tree Problem with General Cost Functions -- Medium-Space Algorithms for Inverse BWT -- Session 6b -- Median Trajectories -- Optimal Cover of Points by Disks in a Simple Polygon -- Stability of ?-Kernels -- The Geodesic Diameter of Polygonal Domains -- Session 7a -- Polyhedral and Algorithmic Properties of Quantified Linear Programs -- Approximating Parameterized Convex Optimization Problems -- Approximation Schemes for Multi-Budgeted Independence Systems -- Session 7b -- Algorithmic Meta-theorems for Restrictions of Treewidth -- Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus -- Constructing the R* Consensus Tree of Two Trees in Subcubic Time. 330 $aThis volume contains the 69 papers presented at the 16th Annual European Symposium on Algorithms (ESA 2010), held in Liverpool during September 6-8, 2010, including three papers by the distinguished invited speakers Artur Czumaj, Herbert Edelsbrunner, and Paolo Ferragina. ESA 2010 was organized as a part of ALGO 2010, which also included the 10th Workshop on Algorithms in Bioinformatics (WABI), the 8th Workshop on Approximation and Online Algorithms (WAOA), and the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS). The European Symposium on Algorithms covers research in the design, use, andanalysisofe'cientalgorithmsanddata structures.As inpreviousyears,the symposium had two tracks: the Design and Analysis Track and the Engineering and Applications Track, each with its own Program Committee. In total 245 papers adhering to the submission guidelines were submitted. Each paper was reviewed by three or four referees. Based on the reviews and the often extensive electronicdiscussionsfollowingthem, thecommittees selected 66papersintotal: 56 (out of 206) to the Design and Analysis Track and 10 (out of 39) to the Engineering andApplicationstrack.We believethat thesepaperstogethermade up a strong and varied program, showing the depth and breadth of current algorithms research. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v6346 606 $aSoftware engineering 606 $aAlgorithms 606 $aComputer networks 606 $aComputer science$xMathematics 606 $aDiscrete mathematics 606 $aComputer graphics 606 $aNumerical analysis 606 $aSoftware Engineering 606 $aAlgorithms 606 $aComputer Communication Networks 606 $aDiscrete Mathematics in Computer Science 606 $aComputer Graphics 606 $aNumerical Analysis 615 0$aSoftware engineering. 615 0$aAlgorithms. 615 0$aComputer networks. 615 0$aComputer science$xMathematics. 615 0$aDiscrete mathematics. 615 0$aComputer graphics. 615 0$aNumerical analysis. 615 14$aSoftware Engineering. 615 24$aAlgorithms. 615 24$aComputer Communication Networks. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aComputer Graphics. 615 24$aNumerical Analysis. 676 $a005.1 701 $aBerg$b Mark de$0534961 701 $aMeyer$b Ulrich$f1971-$01757055 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484493003321 996 $aAlgorithms - ESA 2010$94194694 997 $aUNINA