| 2009 | Sequential cavity method for computing limits of the log-partition function for lattice models. | David Gamarnik, Dmitriy Katz |
| 2009 | Clique-width: on the price of generality. | Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh |
| 2009 | On the bit-complexity of Lempel-Ziv compression. | Paolo Ferragina, Igor Nitto, Rossano Venturini |
| 2009 | Improved approximating algorithms for Directed Steiner Forest. | Moran Feldman, Guy Kortsarz, Zeev Nutov |
| 2009 | Self-overlapping curves revisited. | David Eppstein, Elena Mumford |
| 2009 | Linear-time algorithms for geometric graphs with sublinearly many crossings. | David Eppstein, Michael T. Goodrich, Darren Strash |
| 2009 | Pairing heaps with | Amr Elmasry |
| 2009 | Computing the nucleolus of weighted voting games. | Edith Elkind, Dmitrii V. Pasechnik |
| 2009 | Sorting by placement and shift. | Sergi Elizalde, Peter Winkler |
| 2009 | On the approximability of the maximum feasible subsystem problem with 0/1-coefficients. | Khaled M. Elbassioni, Rajiv Raman, Saurabh Ray, Ren Sitters |
| 2009 | Scalably scheduling processes with arbitrary speedup curves. | Jeff Edmonds, Kirk Pruhs |
| 2009 | Three-coloring triangle-free planar graphs in linear time. | Zdenek Dvork, Ken-ichi Kawarabayashi, Robin Thomas |
| 2009 | Coloring triangle-free graphs on surfaces. | Zdenek Dvork, Daniel Krl, Robin Thomas |
| 2009 | On stars and Steiner stars: II. | Adrian Dumitrescu, Csaba D. Tth, Guangwu Xu |
| 2009 | Biased range trees. | Vida Dujmovic, John Howat, Pat Morin |
| 2009 | Dual-failure distance and connectivity oracles. | Ran Duan, Seth Pettie |
| 2009 | Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. | Ran Duan, Seth Pettie |
| 2009 | (Un)expected behavior of digital search tree profile. | Michael Drmota, Wojciech Szpankowski |
| 2009 | On risks of using cuckoo hashing with simple universal hash classes. | Martin Dietzfelbinger, Ulf Schellbach |
| 2009 | Improved approximation algorithms for scheduling with fixed jobs. | Florian Diedrich, Klaus Jansen |
| 2009 | The geometry of binary search trees. | Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu |
| 2009 | On the complexity of Nash equilibria of action-graph games. | Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant |
| 2009 | Sorting and selection in posets. | Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha J. Riesenfeld, Elad Verbin |
| 2009 | Online story scheduling in web advertising. | Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh, Prabhakar Raghavan |
| 2009 | The cover time of random geometric graphs. | Colin Cooper, Alan M. Frieze |