17. ESA 2009: Copenhagen, Denmark

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 Genc:
  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