• 
  Amos Fiat, Peter Sanders (Eds.): Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings. Springer 2009 Lecture Notes in Computer Science ISBN 978-3-642-04127-3

Invited Talk

• 
  Michael Mitzenmacher: Some Open Questions Related to Cuckoo Hashing. 1-10

Trees

• 
  Martin Fürer: Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks. 11-22
• 
  Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff: Improved Approximation Algorithms for Label Cover Problems. 23-34
• 
  Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno: A Linear Time Algorithm for L(2, 1)-Labeling of Trees. 35-46

Geometry I

• 
  Eyal Ackerman, Rom Pinchasi, Ludmila Scharf, Marc Scherfenberg: On Inducing Polygons and Related Problems. 47-58
• 
  Manuel Caroli, Monique Teillaud: Computing 3D Periodic Triangulations. 59-70
• 
  Therese C. Biedl, Burkay Genç: Cauchy's Theorem for Orthogonal Polyhedra of Genus 0. 71-82

Mathematical Programming

• 
  David Pritchard: Approximability of Sparse Integer Programs. 83-94
• 
  Fabrizio Grandoni, R. Ravi, Mohit Singh: Iterative Rounding for Multi-Objective Optimization Problems. 95-106
• 
  Claudia D'Ambrosio, Jon Lee, Andreas Wächter: A Global-Optimization Algorithm for Mixed-Integer Nonlinear Programs Having Separable Non-convexity. 107-118

Geometry II

• 
  Kevin Buchin: Constructing Delaunay Triangulations along Space-Filling Curves. 119-130
• 
  Adrian Dumitrescu, Minghui Jiang: Piercing Translates and Homothets of a Convex Body. 131-142
• 
  Khaled M. Elbassioni, Kazuhisa Makino, Imran Rauf: Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs. 143-154

Algorithmic Game Theory I

• 
  Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, C. Thach Nguyen: On Revenue Maximization in Second-Price Ad Auctions. 155-166
• 
  Mohammad Mahdian, Grant Wang: Clustering-Based Bidding Languages for Sponsored Search. 167-178
• 
  Martin Hoefer, Alexander Skopalik: Altruism in Atomic Congestion Games. 179-189

Geometry III

• 
  Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson, Michiel H. M. Smid: Geometric Spanners for Weighted Point Sets. 190-202
• 
  Yuval Emek: k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees. 203-214
• 
  Michael Elkin, Shay Solomon: Narrow-Shallow-Low-Light Trees with and without Steiner Points. 215-226

Algorithmic Game Theory II

• 
  Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang, Jiajie Zhu: Bounded Budget Betweenness Centrality Game for Strategic Network Formations. 227-238
• 
  Elliot Anshelevich, Bugra Caskurlu: Exact and Approximate Equilibria for Optimal Group Network Formation. 239-250
• 
  George Christodoulou, Elias Koutsoupias, Paul G. Spirakis: On the Performance of Approximate Equilibria in Congestion Games. 251-262

Navigation and Routing

• 
  Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc: Optimality and Competitiveness of Exploring Polygons by Mobile Robots. 263-274
• 
  Refael Hassin, R. Ravi, F. Sibel Salman: Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links. 275-276
• 
  Navin Goyal, Neil Olver, F. Bruce Shepherd: Dynamic vs. Oblivious Routing in Network Design. 277-288

Invited Talk

• 
  Erik D. Demaine: Algorithms Meet Art, Puzzles, and Magic. 289

Graphs and Point Sets

• 
  Michel Habib, Juraj Stacho: Polynomial-Time Algorithm for the Leafage of Chordal Graphs. 290-300
• 
  Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn, Romeo Rizzi: Breaking the O(m²n) Barrier for Minimum Cycle Bases. 301-312
• 
  Maarten Löffler, Jeff M. Phillips: Shape Fitting on Point Sets with Probability Distributions. 313-324

Bioinformatics

• 
  Jing Xiao, Tiancheng Lou, Tao Jiang: An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants (Extended Abstract). 325-336
• 
  Gerold Jäger, Sharlee Climer, Weixiong Zhang: Complete Parsimony Haplotype Inference Problem and Algorithms. 337-348
• 
  Ross M. McConnell, Yahav Nussbaum: Linear-Time Recognition of Probe Interval Graphs. 349-360

Wireless Communications

• 
  Magnús M. Halldórsson: Wireless Scheduling with Power Control. 361-372
• 
  Chen Avin, Zvi Lotker, Yvonne Anne Pignolet: On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources. 373-384
• 
  Marcel Ochel, Berthold Vöcking: Approximability of OFDMA Scheduling. 385-396

Flows, Matrices, Compression

• 
  Haim Kaplan, Yahav Nussbaum: Maximum Flow in Directed Planar Graphs with Vertex Capacities. 397-407
• 
  Andrzej Lingas: A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication. 408-419
• 
  Paolo Ferragina, Igor Nitto, Rossano Venturini: On Optimally Partitioning a Text to Improve Its Compression. 420-431

Scheduling

• 
  Andreas Karrenbauer, Thomas Rothvoß: An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling. 432-443
• 
  Chandra Chekuri, Sungjin Im, Benjamin Moseley: Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling. 444-455
• 
  György Dósa, Leah Epstein: Preemptive Online Scheduling with Reordering. 456-467

Streaming

• 
  Sumit Ganguly, Christian Sohler: d-Dimensional Knapsack in the Streaming Model. 468-479
• 
  Atish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy: Sparse Cut Projections in Graph Streams. 480-491
• 
  Sebastian Eggert, Lasse Kliemann, Anand Srivastav: Bipartite Graph Matchings in the Semi-streaming Model. 492-503

Online Algorithms

• 
  Andrew McGregor, Krzysztof Onak, Rina Panigrahy: The Oil Searching Problem. 504-515
• 
  David G. Kirkpatrick: Hyperbolic Dovetailing. 516-527

Bluetooth and Dial a Ride

• 
  Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci: On the Expansion and Diameter of Bluetooth-Like Topologies. 528-539
• 
  Inge Li Gørtz, Viswanath Nagarajan, R. Ravi: Minimum Makespan Multi-vehicle Dial-a-Ride. 540-552

Invited Talk

• 
  Noam Nisan: Google's Auction for TV Ads. 553

Decomposition and Covering

• 
  Johan M. M. van Rooij, Jesper Nederlof, Thomas C. van Dijk: Inclusion/Exclusion Meets Measure and Conquer. 554-565
• 
  Johan M. M. van Rooij, Hans L. Bodlaender, Peter Rossmanith: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. 566-577
• 
  Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto: Counting Paths and Packings in Halves. 578-586

Algorithm Engineering

• 
  Daniel Delling, Thomas Pajor, Dorothea Wagner: Accelerating Multi-modal Route Planning by Access-Nodes. 587-598
• 
  Jakub Chaloupka: Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation. 599-610
• 
  Rudolf Fleischer, Xi Wu, Liwei Yuan: Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem. 611-622

Parameterized Algorithms I

• 
  Markus Bläser, Christian Hoffmann: Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. 623-634
• 
  Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo: Kernel Bounds for Disjoint Cycles and Disjoint Paths. 635-646
• 
  Dániel Marx, Igor Razgon: Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem. 647-658

Data Structures

• 
  Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan: Rank-Pairing Heaps. 659-670
• 
  Eric Lehman, Rina Panigrahy: 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit. 671-681
• 
  Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger: Hash, Displace, and Compress. 682-693

Parameterized Algorithms II

• 
  Geevarghese Philip, Venkatesh Raman, Somnath Sikdar: Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels. 694-705
• 
  Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos: Contraction Bidimensionality: The Accurate Picture. 706-717
• 
  Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx: Minimizing Movement: Fixed-Parameter Tractability. 718-729

Hashing and Lowest Common Ancestor

• 
  Jóhannes B. Hreinsson, Morten Krøyer, Rasmus Pagh: Storing a Compressed Function with Constant Time Access. 730-741
• 
  Martin Aumüller, Martin Dietzfelbinger, Michael Rink: Experimental Variations of a Theoretically Good Retrieval Data Structure. 742-751
• 
  Johannes Fischer: Short Labels for Lowest Common Ancestors in Trees. 752-763

Best Paper Awards

• 
  Heidi Gebauer: Disproof of the Neighborhood Conjecture with Implications to SAT. 764-775
• 
  Christoph Dürr, Flavio Guiñez, Martín Matamala: Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard. 776-787