| 2005 | Optimal Hypergraph Tree-Realization. | Ephraim Korach, Margarita Razgon |
| 2005 | Algorithms Based on the Treewidth of Sparse Graphs. | Joachim Kneis, Daniel Mlle, Stefan Richter, Peter Rossmanith |
| 2005 | Approximation Algorithms for the Weighted Independent Set Problem. | Akihisa Kako, Takao Ono, Tomio Hirata, Magns M. Halldrsson |
| 2005 | Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time. | Pinar Heggernes, Daniel Lokshtanov |
| 2005 | Channel Assignment and Improper Choosability of Graphs. | Frdric Havet, Jean-Sbastien Sereni |
| 2005 | Minimizing NLC-Width is NP-Complete. | Frank Gurski, Egon Wanke |
| 2005 | Hypertree Decompositions: Structure, Algorithms, and Applications. | Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, Francesco Scarcello |
| 2005 | Acyclic Choosability of Graphs with Small Maximum Degree. | Daniel Gonalves, Mickal Montassier |
| 2005 | Complete Graph Drawings Up to Triangle Mutations. | Emeric Gioan |
| 2005 | Computing the Tutte Polynomial on Graphs of Bounded Clique-Width. | Omer Gimnez, Petr Hlinen, Marc Noy |
| 2005 | Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model. | Joachim Giesen, Dieter Mitsche |
| 2005 | The Computational Complexity of Delay Management. | Michael Gatto, Riko Jacob, Leon Peeters, Anita Schbel |
| 2005 | Computing Branchwidth Via Efficient Triangulations and Blocks. | Fedor V. Fomin, Frdric Mazoit, Ioan Todinca |
| 2005 | Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms. | Jir Fiala, Danil Paulusma, Jan Arne Telle |
| 2005 | On Randomized Broadcasting in Star Graphs. | Robert Elssser, Thomas Sauerwald |
| 2005 | Extending the Tractability Border for Closest Leaf Powers. | Michael Dom, Jiong Guo, Falk Hffner, Rolf Niedermeier |
| 2005 | On the Fixed-Parameter Enumerability of Cluster Editing. | Peter Damaschke |
| 2005 | Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs. | Christophe Crespelle, Christophe Paul |
| 2005 | Collective Tree 1-Spanners for Interval Graphs. | Derek G. Corneil, Feodor F. Dragan, Ekkehard Khler, Chenyu Yan |
| 2005 | Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey. | Mathilde Bouvel, Vladimir Grebinski, Gregory Kucherov |
| 2005 | Induced Subgraphs of Bounded Degree and Bounded Treewidth. | Prosenjit Bose, Vida Dujmovic, David R. Wood |
| 2005 | Locally Consistent Constraint Satisfaction Problems with Binary Constraints. | Manuel Bodirsky, Daniel Krl |
| 2005 | Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints. | Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stphane Vialette |
| 2005 | Computation of Chromatic Polynomials Using Triangulations and Clique Trees. | Pascal Berthom, Sylvain Lebresne, Kim Nguyen |
| 2005 | Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny. | Anne Berry, Alain Sigayret, Jeremy P. Spinrad |