List of accepted papers for ESA 2009:


Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn and Romeo Rizzi. 
Breaking the O(m^2 n) Barrier for Minimum Cycle Basis

Eyal Ackerman, Rom Pinchasi, Ludmila Scharf and Marc Scherfenberg. 
On Inducing Polygons and Related Problems

Martin Aum?ller, Martin Dietzfelbinger and Michael Rink. 
Experimental variations of a theoretically good retrieval data structure

Chen Avin, Zvi Lotker and Yvonne Anne Pignolet. 
On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources

Yossi Azar, Benjamin Birnbaum, Anna Karlin and Thach Nguyen. 
On Revenue Maximization in Second-Price Ad Auctions

Elliot Anshelevich and Bugra Caskurlu. 
Exact and Approximate Equilibria for Optimal Group Network Formation

Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson and Michiel Smid. 
Geometric Spanners for Weighted Point Sets

Therese Biedl and Burkay Genc. 
Cauchy's theorem for orthogonal polyhedra of genus 0

Markus Blaeser and Christian Hoffmann. 
Fast Computation of Interlace Polynomials on Graphs of Bounded Treewidth

Hans L. Bodlaender, Stephan Thomasse and Anders Yeo. 
Kernel Bounds for Disjoint Cycles and Disjoint Paths

Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang and Jiajie Zhu. 
Bounded Budget Betweenness Centrality Game for Strategic Network Formations

Andreas Bjorklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto. 
Counting Paths and Packings in Halves

Djamal Belazzougui, Fabiano Botelho and Martin Dietzfelbinger. 
Hash, displace, and compress

Kevin Buchin. 
Constructing Delaunay Triangulations along Space-Filling Curves

Moses Charikar, MohammadTaghi Hajiaghayi and Howard Karloff. 
Improved Approximation Algorithms for Label Cover Problems

Jurek Czyzowicz, Arnaud Labourel and Andrzej Pelc. 
Optimality and Competitiveness of Exploring Polygons by Mobile Robots

George Christodoulou, Elias Koutsoupias and Paul Spirakis. 
On the performance of approximate equilibria in congestion games

Jakub Chaloupka. 
Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation

Manuel Caroli and Monique Teillaud. 
Computing 3D Periodic Triangulations

Chandra Chekuri, Sungjin Im and Benjamin Moseley. 
Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling

Adrian Dumitrescu and Minghui Jiang. 
Piercing translates and homothets of a convex body

Gyorgy Dosa and Leah Epstein. 
Preemptive online scheduling with reordering

Atish Das Sarma, Sreenivas Gollapudi and Rina Panigrahy. 
Sparse Cut Projections in Graph Streams

Daniel Delling, Thomas Pajor and Dorothea Wagner. 
Accelerating Multi-Modal Route Planning by Access-Nodes

Erik D. Demaine, MohammadTaghi Hajiaghayi and D?niel Marx. 
Minimizing Movement: Fixed-Parameter Tractability

Claudia D'Ambrosio, Jon Lee and Andreas Waechter. 
A global-optimization algorithm for mixed-integer nonlinear programs having separable non-convexity

Christoph D?rr, Flavio Gui?ez and Mart?n Matamala. 
Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard

Yuval Emek. 
k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees

Michael Elkin and Shay Solomon. 
Narrow-Shallow-Low-Light Trees with and without Steiner Points

Sebastian Eggert, Lasse Kliemann and Anand Srivastav. 
Bipartite Graph Matchings in the Semi-Streaming Model

Khaled Elbassioni, Kazuhisa Makino and Imran Rauf. 
Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs

Johannes Fischer. 
Short Labels for Lowest Common Ancestors in Trees

Fedor Fomin, Petr Golovach and Dimitrios Thilikos. 
Contraction Bidimensionality: the accurate picture

Paolo Ferragina, Igor Nitto and Rossano Venturini. 
On optimally partitioning a text to improve its compression

Rudolf Fleischer, Xi Wu and Liwei Yuan. 
Experimental study of FPT algorithms for the directed feedback vertex set problem

Martin F?rer. 
E?cient Computation of the Characteristic Polynomial of a Tree and Related Tasks

Heidi Gebauer. 
Disproof of the Neighborhood Conjecture with Implications to SAT

Fabrizio Grandoni, Ravi R. and Mohit Singh. 
Iterative Rounding for Multi-Objective Optimization Problems

Sumit Ganguly and Christian Sohler. 
d-dimensional Knapsack in the Streaming Model

Navin Goyal, Neil Olver and Bruce Shepherd. 
Dynamic vs Oblivious Routing in Network Design

Johannes B Hreinsson, Morten Kr?yer and Rasmus Pagh. 
Storing a Compressed Function with Constant Time Access

Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono and Yushi Uno. 
A linear time algorithm for L(2, 1)-labeling of trees

Martin Hoefer and Alexander Skopalik. 
Altruism in Atomic Congestion Games

Rafael Hassin, R Ravi and Fatma Sibel Salman. 
Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links

Gerold Jaeger, Sharlee Climer and Weixiong Zhang. 
Complete Parsimony Haplotype Inference Problem and Algorithms

Haim Kaplan and Yahav Nussbaum. 
Maximum Flow in Directed Planar Graphs with Vertex Capacities

David Kirkpatrick. 
Hyperbolic dovetailing

Andreas Karrenbauer and Thomas Rothvoss. 
An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

Maarten L?ffler and Jeff Phillips. 
Shape Fitting on Point Sets with Probability Distributions

Inge Li G?rtz, Viswanath Nagarajan and R Ravi. 
Minimum Makespan Multi-vehicle Dial-a-Ride

Andrzej Lingas. 
A fast output-sensitive algorithm for Boolean matrix multiplication

Ross McConnell and Yahav Nussbaum. 
Linear-time recognition of probe interval graphs

Johan M. M. van Rooij, Hans L. Bodlaender and Peter Rossmanith. 
Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

Johan M. M. van Rooij, Jesper Nederlof and Thomas C. van Dijk. 
Inclusion/Exclusion Meets Measure and Conquer: Exact algorithms for counting dominating sets

Andrew McGregor, Krzysztof Onak and Rina Panigrahy. 
The Oil Searching Problem

D?niel Marx and Igor Razgon. 
Constant ratio fixed-parameter approximation of the edge multicut problem

Magnus M. Halldorsson. 
Wireless scheduling with power control

Mohammad Mahdian and Grant Wang. 
Clustering-Based Bidding Languages for Sponsored Search

Marcel Ochel and Berthold V?cking. 
Approximability of OFDMA Scheduling

David Pritchard. 
Approximability of Sparse Integer Programs

Alberto Pettarin, Andrea Pietracaprina and Geppino Pucci. 
On the Expansion and Diameter of Bluetooth-like Topologies

Rina Panigrahy and Eric Lehman. 
3.5-Way Cuckoo Hashing for the Price of 2

Geevarghese Philip, Venkatesh Raman and Somnath Sikdar. 
Solving Dominating Set in Larger Classes of  Graphs: FPT Algorithms and Polynomial Kernels

Juraj Stacho and Michel Habib. 
Polynomial-time algorithm for the leafage of chordal graphs

Siddhartha Sen, Bernhard Haeupler and Robert E. Tarjan. 
Rank-Pairing Heaps

Jing Xiao, Tiancheng Lou and Tao Jiang. 
An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants