Algorithms - ESA 2009 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, Proceedings / [electronic resource] :
edited by Amos Fiat, Peter Sanders.
- 1st ed. 2009.
- XIX, 790 p. online resource.
- Theoretical Computer Science and General Issues, 5757 2512-2029 ; .
- Theoretical Computer Science and General Issues, 5757 .
Invited 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, andMagic -- 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.
This 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.
9783642041280
10.1007/978-3-642-04128-0 doi
Computer programming. Algorithms. Information retrieval. Computer architecture. Artificial intelligence--Data processing. Computer science--Mathematics. Computer networks . Programming Techniques. Algorithms. Data Storage Representation. Data Science. Mathematics of Computing. Computer Communication Networks.