LEADER 08455nam 22007935 450 001 996465672303316 005 20230406062035.0 010 $a3-642-04128-0 024 7 $a10.1007/978-3-642-04128-0 035 $a(CKB)1000000000798289 035 $a(SSID)ssj0000316173 035 $a(PQKBManifestationID)11261608 035 $a(PQKBTitleCode)TC0000316173 035 $a(PQKBWorkID)10263761 035 $a(PQKB)10579904 035 $a(DE-He213)978-3-642-04128-0 035 $a(MiAaPQ)EBC3064588 035 $a(PPN)139955356 035 $a(EXLCZ)991000000000798289 100 $a20100301d2009 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithms - ESA 2009$b[electronic resource] $e17th Annual European Symposium, Copenhagen, Denmark, September 7-9, Proceedings /$fedited by Amos Fiat, Peter Sanders 205 $a1st ed. 2009. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2009. 215 $a1 online resource (XIX, 790 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5757 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-642-04127-2 320 $aIncludes bibliographical references and index. 327 $aInvited Talk -- Some Open Questions Related to Cuckoo Hashing -- Trees -- Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks -- Improved Approximation Algorithms for Label Cover Problems -- A Linear Time Algorithm for L(2,1)-Labeling of Trees -- Geometry I -- On Inducing Polygons and Related Problems -- Computing 3D Periodic Triangulations -- Cauchy?s Theorem for Orthogonal Polyhedra of Genus 0 -- Mathematical Programming -- Approximability of Sparse Integer Programs -- Iterative Rounding for Multi-Objective Optimization Problems -- A Global-Optimization Algorithm for Mixed-Integer Nonlinear Programs Having Separable Non-convexity -- Geometry II -- Constructing Delaunay Triangulations along Space-Filling Curves -- Piercing Translates and Homothets of a Convex Body -- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs -- Algorithmic Game Theory I -- On Revenue Maximization in Second-Price Ad Auctions -- Clustering-Based Bidding Languages for Sponsored Search -- Altruism in Atomic Congestion Games -- Geometry III -- Geometric Spanners for Weighted Point Sets -- k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees -- Narrow-Shallow-Low-Light Trees with and without Steiner Points -- Algorithmic Game Theory II -- Bounded Budget Betweenness Centrality Game for Strategic Network Formations -- Exact and Approximate Equilibria for Optimal Group Network Formation -- On the Performance of Approximate Equilibria in Congestion Games -- Navigation and Routing -- Optimality and Competitiveness of Exploring Polygons by Mobile Robots -- Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links -- Dynamic vs. Oblivious Routing in Network Design -- Invited Talk -- Algorithms Meet Art, Puzzles, and Magic -- Graphs and Point Sets -- Polynomial-Time Algorithm for the Leafage of Chordal Graphs -- Breaking the O(m 2 n) Barrier for Minimum Cycle Bases -- Shape Fitting on Point Sets with Probability Distributions -- Bioinformatics -- An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants (Extended Abstract) -- Complete Parsimony Haplotype Inference Problem and Algorithms -- Linear-Time Recognition of Probe Interval Graphs -- Wireless Communications -- Wireless Scheduling with Power Control -- On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources -- Approximability of OFDMA Scheduling -- Flows, Matrices, Compression -- Maximum Flow in Directed Planar Graphs with Vertex Capacities -- A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication -- On Optimally Partitioning a Text to Improve Its Compression -- Scheduling -- An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling -- Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling -- Preemptive Online Scheduling with Reordering -- Streaming -- d-Dimensional Knapsack in the Streaming Model -- Sparse Cut Projections in Graph Streams -- Bipartite Graph Matchings in the Semi-streaming Model -- Online Algorithms -- The Oil Searching Problem -- Hyperbolic Dovetailing -- Bluetooth and Dial a Ride -- On the Expansion and Diameter of Bluetooth-Like Topologies -- Minimum Makespan Multi-vehicle Dial-a-Ride -- Invited Talk -- Google?s Auction for TV Ads -- Decomposition and Covering -- Inclusion/Exclusion Meets Measure and Conquer -- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution -- Counting Paths and Packings in Halves -- Algorithm Engineering -- Accelerating Multi-modal Route Planning by Access-Nodes -- Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation -- Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem -- Parameterized Algorithms I -- Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth -- Kernel Bounds for Disjoint Cycles and Disjoint Paths -- Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem -- Data Structures -- Rank-Pairing Heaps -- 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit -- Hash, Displace, and Compress -- Parameterized Algorithms II -- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels -- Contraction Bidimensionality: The Accurate Picture -- Minimizing Movement: Fixed-Parameter Tractability -- Hashing and Lowest Common Ancestor -- Storing a Compressed Function with Constant Time Access -- Experimental Variations of a Theoretically Good Retrieval Data Structure -- Short Labels for Lowest Common Ancestors in Trees -- Best Paper Awards -- Disproof of the Neighborhood Conjecture with Implications to SAT -- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard. 330 $aThis book constitutes the refereed proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009, held in Copenhagen, Denmark, in September 2009 in the context of the combined conference ALGO 2009. The 67 revised full papers presented together with 3 invited lectures were carefully reviewed and selected: 56 papers out of 222 submissions for the design and analysis track and 10 out of 36 submissions in the engineering and applications track. The papers are organized in topical sections on trees, geometry, mathematical programming, algorithmic game theory, navigation and routing, graphs and point sets, bioinformatics, wireless communiations, flows, matrices, compression, scheduling, streaming, online algorithms, bluetooth and dial a ride, decomposition and covering, algorithm engineering, parameterized algorithms, data structures, and hashing and lowest common ancestor. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5757 606 $aComputer programming 606 $aAlgorithms 606 $aInformation retrieval 606 $aComputer architecture 606 $aArtificial intelligence?Data processing 606 $aComputer science?Mathematics 606 $aComputer networks 606 $aProgramming Techniques 606 $aAlgorithms 606 $aData Storage Representation 606 $aData Science 606 $aMathematics of Computing 606 $aComputer Communication Networks 615 0$aComputer programming. 615 0$aAlgorithms. 615 0$aInformation retrieval. 615 0$aComputer architecture. 615 0$aArtificial intelligence?Data processing. 615 0$aComputer science?Mathematics. 615 0$aComputer networks. 615 14$aProgramming Techniques. 615 24$aAlgorithms. 615 24$aData Storage Representation. 615 24$aData Science. 615 24$aMathematics of Computing. 615 24$aComputer Communication Networks. 676 $a005.11 702 $aFiat$b Amos$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aSanders$b Peter$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a996465672303316 996 $aAlgorithms - ESA 2009$9773717 997 $aUNISA