| 2009 | Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem. | Dniel Marx, Igor Razgon |
| 2009 | Clustering-Based Bidding Languages for Sponsored Search. | Mohammad Mahdian, Grant Wang |
| 2009 | Shape Fitting on Point Sets with Probability Distributions. | Maarten Lffler, Jeff M. Phillips |
| 2009 | A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication. | Andrzej Lingas |
| 2009 | 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit. | Eric P. Lehman, Rina Panigrahy |
| 2009 | Hyperbolic Dovetailing. | David G. Kirkpatrick |
| 2009 | An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling. | Andreas Karrenbauer, Thomas Rothvo |
| 2009 | Maximum Flow in Directed Planar Graphs with Vertex Capacities. | Haim Kaplan, Yahav Nussbaum |
| 2009 | Complete Parsimony Haplotype Inference Problem and Algorithms. | Gerold Jger, Sharlee Climer, Weixiong Zhang |
| 2009 | Storing a Compressed Function with Constant Time Access. | Jhannes B. Hreinsson, Morten Kryer, Rasmus Pagh |
| 2009 | Altruism in Atomic Congestion Games. | Martin Hoefer, Alexander Skopalik |
| 2009 | A Linear Time Algorithm for | Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno |
| 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. | Magns M. Halldrsson |
| 2009 | Rank-Pairing Heaps. | Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan |
| 2009 | Polynomial-Time Algorithm for the Leafage of Chordal Graphs. | Michel Habib, Juraj Stacho |
| 2009 | Iterative Rounding for Multi-Objective Optimization Problems. | Fabrizio Grandoni, R. Ravi, Mohit Singh |
| 2009 | Dynamic vs. Oblivious Routing in Network Design. | Navin Goyal, Neil Olver, F. Bruce Shepherd |
| 2009 | Minimum Makespan Multi-vehicle Dial-a-Ride. | Inge Li Grtz, Viswanath Nagarajan, R. Ravi |
| 2009 | Disproof of the Neighborhood Conjecture with Implications to SAT. | Heidi Gebauer |
| 2009 | Untitled record | Sumit Ganguly, Christian Sohler |
| 2009 | Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks. | Martin Frer |
| 2009 | Contraction Bidimensionality: The Accurate Picture. | Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos |
| 2009 | Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem. | Rudolf Fleischer, Xi Wu, Liwei Yuan |
| 2009 | Short Labels for Lowest Common Ancestors in Trees. | Johannes Fischer |