| 2009 | 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit. Eric Lehman, Rina Panigrahy |
| 2009 | A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication. Andrzej Lingas |
| 2009 | A Global-Optimization Algorithm for Mixed-Integer Nonlinear Programs Having Separable Non-convexity. Claudia D'Ambrosio, Jon Lee, Andreas Wächter |
| 2009 | A Linear Time Algorithm for Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno |
| 2009 | Accelerating Multi-modal Route Planning by Access-Nodes. Daniel Delling, Thomas Pajor, Dorothea Wagner |
| 2009 | Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings Amos Fiat, Peter Sanders |
| 2009 | Algorithms Meet Art, Puzzles, and Magic. Erik D. Demaine |
| 2009 | Altruism in Atomic Congestion Games. Martin Hoefer, Alexander Skopalik |
| 2009 | An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling. Andreas Karrenbauer, Thomas Rothvoß |
| 2009 | An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants (Extended Abstract). Jing Xiao, Tiancheng Lou, Tao Jiang |
| 2009 | Approximability of OFDMA Scheduling. Marcel Ochel, Berthold Vöcking |
| 2009 | Approximability of Sparse Integer Programs. David Pritchard |
| 2009 | Bipartite Graph Matchings in the Semi-streaming Model. Sebastian Eggert, Lasse Kliemann, Anand Srivastav |
| 2009 | Bounded Budget Betweenness Centrality Game for Strategic Network Formations. Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang, Jiajie Zhu |
| 2009 | Breaking the O(m Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn, Romeo Rizzi |
| 2009 | Cauchy's Theorem for Orthogonal Polyhedra of Genus 0. Therese Biedl, Burkay Genç |
| 2009 | Clustering-Based Bidding Languages for Sponsored Search. Mohammad Mahdian, Grant Wang |
| 2009 | Complete Parsimony Haplotype Inference Problem and Algorithms. Gerold Jäger, Sharlee Climer, Weixiong Zhang |
| 2009 | Computing 3D Periodic Triangulations. Manuel Caroli, Monique Teillaud |
| 2009 | Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem. Dániel Marx, Igor Razgon |
| 2009 | Constructing Delaunay Triangulations along Space-Filling Curves. Kevin Buchin |
| 2009 | Contraction Bidimensionality: The Accurate Picture. Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos |
| 2009 | Counting Paths and Packings in Halves. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |
| 2009 | Disproof of the Neighborhood Conjecture with Implications to SAT. Heidi Gebauer |
| 2009 | Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. Johan M. M. van Rooij, Hans L. Bodlaender, Peter Rossmanith |
| 2009 | Dynamic vs. Oblivious Routing in Network Design. Navin Goyal, Neil Olver, F. Bruce Shepherd |
| 2009 | Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks. Martin Fürer |
| 2009 | Exact and Approximate Equilibria for Optimal Group Network Formation. Elliot Anshelevich, Bugra Çaskurlu |
| 2009 | Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem. Rudolf Fleischer, Xi Wu, Liwei Yuan |
| 2009 | Experimental Variations of a Theoretically Good Retrieval Data Structure. Martin Aumüller, Martin Dietzfelbinger, Michael Rink |
| 2009 | Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. Markus Bläser, Christian Hoffmann |
| 2009 | Geometric Spanners for Weighted Point Sets. Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson, Michiel H. M. Smid |
| 2009 | Google's Auction for TV Ads. Noam Nisan |
| 2009 | Hash, Displace, and Compress. Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger |
| 2009 | Hyperbolic Dovetailing. David G. Kirkpatrick |
| 2009 | Improved Approximation Algorithms for Label Cover Problems. Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff |
| 2009 | Inclusion/Exclusion Meets Measure and Conquer. Johan M. M. van Rooij, Jesper Nederlof, Thomas C. van Dijk |
| 2009 | Iterative Rounding for Multi-Objective Optimization Problems. Fabrizio Grandoni, R. Ravi, Mohit Singh |
| 2009 | Kernel Bounds for Disjoint Cycles and Disjoint Paths. Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo |
| 2009 | Linear-Time Recognition of Probe Interval Graphs. Ross M. McConnell, Yahav Nussbaum |
| 2009 | Maximum Flow in Directed Planar Graphs with Vertex Capacities. Haim Kaplan, Yahav Nussbaum |
| 2009 | Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling. Chandra Chekuri, Sungjin Im, Benjamin Moseley |
| 2009 | Minimizing Movement: Fixed-Parameter Tractability. Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx |
| 2009 | Minimum Makespan Multi-vehicle Dial-a-Ride. Inge Li Gørtz, Viswanath Nagarajan, R. Ravi |
| 2009 | Narrow-Shallow-Low-Light Trees with and without Steiner Points. Michael Elkin, Shay Solomon |
| 2009 | On Inducing Polygons and Related Problems. Eyal Ackerman, Rom Pinchasi, Ludmila Scharf, Marc Scherfenberg |
| 2009 | On Optimally Partitioning a Text to Improve Its Compression. Paolo Ferragina, Igor Nitto, Rossano Venturini |
| 2009 | On Revenue Maximization in Second-Price Ad Auctions. Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, C. Thach Nguyen |
| 2009 | On the Expansion and Diameter of Bluetooth-Like Topologies. Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci |
| 2009 | On the Performance of Approximate Equilibria in Congestion Games. George Christodoulou, Elias Koutsoupias, Paul G. Spirakis |
| 2009 | On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources. Chen Avin, Zvi Lotker, Yvonne-Anne Pignolet |
| 2009 | Optimality and Competitiveness of Exploring Polygons by Mobile Robots. Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc |
| 2009 | Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs. Khaled M. Elbassioni, Kazuhisa Makino, Imran Rauf |
| 2009 | Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation. Jakub Chaloupka |
| 2009 | Piercing Translates and Homothets of a Convex Body. Adrian Dumitrescu, Minghui Jiang |
| 2009 | Polynomial-Time Algorithm for the Leafage of Chordal Graphs. Michel Habib, Juraj Stacho |
| 2009 | Preemptive Online Scheduling with Reordering. György Dósa, Leah Epstein |
| 2009 | Rank-Pairing Heaps. Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan |
| 2009 | Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard. Christoph Dürr, Flavio Guiñez, Martín Matamala |
| 2009 | Shape Fitting on Point Sets with Probability Distributions. Maarten Löffler, Jeff M. Phillips |
| 2009 | Short Labels for Lowest Common Ancestors in Trees. Johannes Fischer |
| 2009 | Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels. Geevarghese Philip, Venkatesh Raman, Somnath Sikdar |
| 2009 | Some Open Questions Related to Cuckoo Hashing. Michael Mitzenmacher |
| 2009 | Sparse Cut Projections in Graph Streams. Atish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy |
| 2009 | Storing a Compressed Function with Constant Time Access. Jóhannes B. Hreinsson, Morten Krøyer, Rasmus Pagh |
| 2009 | The Oil Searching Problem. Andrew McGregor, Krzysztof Onak, Rina Panigrahy |
| 2009 | Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links. Refael Hassin, R. Ravi, F. Sibel Salman |
| 2009 | Wireless Scheduling with Power Control. Magnús M. Halldórsson |