Algorithms - ESA 2009 : 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, Proceedings / edited by Amos Fiat, Peter Sanders.

Format:

Book

Contributor:

Fiat, Amos, editor.

Sanders, Peter, 1967- editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 5757.

Theoretical Computer Science and General Issues ; 5757

Language:

English

Subjects (All):

Computer programming.

Algorithms.

Data structures (Computer science).

Computer science--Mathematics.

Computer science.

Computer networks.

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Data Storage Representation.

Data Structures.

Mathematics of Computing.

Computer Communication Networks.

Local Subjects:

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Data Storage Representation.

Data Structures.

Mathematics of Computing.

Computer Communication Networks.

Physical Description:

1 online resource (XIX, 790 pages).

Edition:

First edition 2009.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2009.

System Details:

text file PDF

Summary:

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.

Contents:

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, 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

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.

Other Format:

Printed edition:

ISBN:

978-3-642-04128-0

9783642041280

Access Restriction:

Restricted for use by site license.