| 2005 | Dense Subgraph Problems with Output-Density Conditions. | Akiko Suzuki, Takeshi Tokuyama |
| 2005 | Fast k-Means Algorithms with Constant Approximation. | Mingjun Song, Sanguthevar Rajasekaran |
| 2005 | A 1.5-Approximation of the Minimal Manhattan Network Problem. | Sebastian Seibert, Walter Unger |
| 2005 | Minimizing a Monotone Concave Function with Laminar Covering Constraints. | Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige |
| 2005 | Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs. | Christoforos L. Raptopoulos, Paul G. Spirakis |
| 2005 | A Simple Optimal Randomized Algorithm for Sorting on the PDM. | Sanguthevar Rajasekaran, Sandeep Sen |
| 2005 | Solving Minimum Weight Exact Satisfiability in Time | Stefan Porschen |
| 2005 | Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time. | Seth Pettie |
| 2005 | Algorithms for Local Forest Similarity. | Zeshan Peng |
| 2005 | Representation of Graphs by OBDDs. | Robin Nunkesser, Philipp Woelfel |
| 2005 | Fast Algorithms for Computing the Tripartition-Based Distance Between Phylogenetic Networks. | Nguyen Bao Nguyen, C. Thach Nguyen, Wing-Kin Sung |
| 2005 | An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques. | Martin Nehz, Daniel Olejr |
| 2005 | Hardness and Approximation of Octilinear Steiner Trees. | Matthias Mller-Hannemann, Anna Schulze |
| 2005 | On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems. | Jrme Monnot |
| 2005 | Network Game with Attacker and Protector Entities. | Marios Mavronicolas, Vicky G. Papadopoulou, Anna Philippou, Paul G. Spirakis |
| 2005 | Smoothed Analysis of Binary Search Trees. | Bodo Manthey, Rdiger Reischuk |
| 2005 | Simulating Undirected | Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-yi Cai |
| 2005 | Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem. | Lan Liu, Xi Chen, Jing Xiao, Tao Jiang |
| 2005 | Almost Optimal Solutions for Bin Coloring Problems. | Mingen Lin, Zhiyong Lin, Jinhui Xu |
| 2005 | Randomized Algorithm for the Sum Selection Problem. | Tien-Ching Lin, D. T. Lee |
| 2005 | The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree. | Andrew Lim, Fan Wang, Zhou Xu |
| 2005 | Improved Approximate String Matching Using Compressed Suffix Data Structures. | Tak Wah Lam, Wing-Kin Sung, Swee-Seong Wong |
| 2005 | Approximate Colored Range Queries. | Ying Kit Lai, Chung Keung Poon, Benyun Shi |
| 2005 | On Bounded Load Routings for Modeling | Adrian Kosowski, Michal Malafiejski, Pawel Zylinski |
| 2005 | Counting Stable Strategies in Random Evolutionary Games. | Spyros C. Kontogiannis, Paul G. Spirakis |