| 2005 | All maximal independent sets and dynamic dominance for sparse graphs. | David Eppstein |
| 2005 | Improved schedule for radio broadcast. | Michael Elkin, Guy Kortsarz |
| 2005 | An improved approximation algorithm for virtual private network design. | Friedrich Eisenbrand, Fabrizio Grandoni |
| 2005 | Matrix rounding with low error in small submatrices. | Benjamin Doerr |
| 2005 | Delaunay triangulations approximate anchor hulls. | Tamal K. Dey, Joachim Giesen, Samrat Goswami |
| 2005 | Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. | Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2005 | Bidimensionality: new connections between FPT algorithms and PTASs. | Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2005 | Adaptivity and approximation for stochastic packing problems. | Brian C. Dean, Michel X. Goemans, Jan Vondrk |
| 2005 | Substring compression problems. | Graham Cormode, S. Muthukrishnan |
| 2005 | Sparse source-wise and pair-wise distance preservers. | Don Coppersmith, Michael Elkin |
| 2005 | The cover time of two classes of random graphs. | Colin Cooper, Alan M. Frieze |
| 2005 | Sampling regular graphs and a peer-to-peer network. | Colin Cooper, Martin E. Dyer, Catherine S. Greenhill |
| 2005 | A spectral heuristic for bisecting random graphs. | Amin Coja-Oghlan |
| 2005 | On the polynomial time computation of equilibria for certain exchange economies. | Bruno Codenotti, Sriram V. Pemmaraju, Kasturi R. Varadarajan |
| 2005 | Approximating k-median with non-uniform capacities. | Julia Chuzhoy, Yuval Rabani |
| 2005 | On the approximability of some network design problems. | Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha |
| 2005 | External-memory exact and approximate all-pairs shortest-paths in undirected graphs. | Rezaul Alam Chowdhury, Vijaya Ramachandran |
| 2005 | Approximation hardness of optimization problems in intersection graphs of | Miroslav Chlebk, Janka Chlebkov |
| 2005 | Manifold reconstruction from point samples. | Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos |
| 2005 | Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. | Shuchi Chawla, Anupam Gupta, Harald Rcke |
| 2005 | A tight threshold for metric Ramsey phenomena. | Moses Charikar, Adriana Karagiozova |
| 2005 | Dynamic dictionary matching and compressed suffix trees. | Ho-Leung Chan, Wing-Kai Hon, Tak Wah Lam, Kunihiko Sadakane |
| 2005 | On hierarchical routing in doubling metrics. | Hubert Tsz-Hong Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou |
| 2005 | Finding the shortest bottleneck edge in a parametric minimum spanning tree. | Timothy M. Chan |
| 2005 | On levels in arrangements of surfaces in three dimensions. | Timothy M. Chan |