| 2005 | Acyclic Choosability of Graphs with Small Maximum Degree. Daniel Gonçalves, Mickaël Montassier |
| 2005 | Adding an Edge in a Cograph. Stavros D. Nikolopoulos, Leonidas Palios |
| 2005 | Algebraic Operations on PQ Trees and Modular Decomposition Trees. Ross M. McConnell, Fabien de Montgolfier |
| 2005 | Algorithms Based on the Treewidth of Sparse Graphs. Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith |
| 2005 | Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms. Jirí Fiala, Daniël Paulusma, Jan Arne Telle |
| 2005 | Approximating Rank-Width and Clique-Width Quickly. Sang-il Oum |
| 2005 | Approximation Algorithms for Unit Disk Graphs. Erik Jan van Leeuwen |
| 2005 | Approximation Algorithms for the Bi-criteria Weighted max-cut Problem. Eric Angel, Evripidis Bampis, Laurent Gourvès |
| 2005 | Approximation Algorithms for the Weighted Independent Set Problem. Akihisa Kako, Takao Ono, Tomio Hirata, Magnús M. Halldórsson |
| 2005 | Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model. Joachim Giesen, Dieter Mitsche |
| 2005 | Channel Assignment and Improper Choosability of Graphs. Frédéric Havet, Jean-Sébastien Sereni |
| 2005 | Collective Tree 1-Spanners for Interval Graphs. Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Chenyu Yan |
| 2005 | Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey. Mathilde Bouvel, Vladimir Grebinski, Gregory Kucherov |
| 2005 | Complete Graph Drawings Up to Triangle Mutations. Emeric Gioan |
| 2005 | Computation of Chromatic Polynomials Using Triangulations and Clique Trees. Pascal Berthomé, Sylvain Lebresne, Kim Nguyen |
| 2005 | Computing Branchwidth Via Efficient Triangulations and Blocks. Fedor V. Fomin, Frédéric Mazoit, Ioan Todinca |
| 2005 | Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time. Daniel Meister |
| 2005 | Computing the Tutte Polynomial on Graphs of Bounded Clique-Width. Omer Giménez, Petr Hlinený, Marc Noy |
| 2005 | Domination Search on Graphs with Low Dominating-Target-Number. Divesh Aggarwal, Shashank K. Mehta, Jitender S. Deogun |
| 2005 | Extending the Tractability Border for Closest Leaf Powers. Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier |
| 2005 | Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny. Anne Berry, Alain Sigayret, Jeremy P. Spinrad |
| 2005 | Finding Disjoint Paths on Directed Acyclic Graphs. Torsten Tholey |
| 2005 | Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints. Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stéphane Vialette |
| 2005 | Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs. Christophe Crespelle, Christophe Paul |
| 2005 | Generating Colored Trees. Shin-Ichi Nakano, Takeaki Uno |
| 2005 | Graph-Theoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers Dieter Kratsch |
| 2005 | Hypertree Decompositions: Structure, Algorithms, and Applications. Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, Francesco Scarcello |
| 2005 | Induced Subgraphs of Bounded Degree and Bounded Treewidth. Prosenjit Bose, Vida Dujmovic, David R. Wood |
| 2005 | Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs. Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara |
| 2005 | Locally Consistent Constraint Satisfaction Problems with Binary Constraints. Manuel Bodirsky, Daniel Král |
| 2005 | Minimizing NLC-Width is NP-Complete. Frank Gurski, Egon Wanke |
| 2005 | Network Discovery and Verification. Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, L. Shankar Ram |
| 2005 | On Randomized Broadcasting in Star Graphs. Robert Elsässer, Thomas Sauerwald |
| 2005 | On Stable Cutsets in Claw-Free Graphs and Planar Graphs. Van Bang Le, Raffaele Mosca, Haiko Müller |
| 2005 | On the Fixed-Parameter Enumerability of Cluster Editing. Peter Damaschke |
| 2005 | Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time. Pinar Heggernes, Daniel Lokshtanov |
| 2005 | Optimal Hypergraph Tree-Realization. Ephraim Korach, Margarita Razgon |
| 2005 | Recognizing HHDS-Free Graphs. Stavros D. Nikolopoulos, Leonidas Palios |
| 2005 | Roman Domination over Some Graph Classes. Mathieu Liedloff, Ton Kloks, Jiping Liu, Sheng-Lung Peng |
| 2005 | The Computational Complexity of Delay Management. Michael Gatto, Riko Jacob, Leon Peeters, Anita Schöbel |
| 2005 | Ultimate Generalizations of LexBFS and LEX M. Anne Berry, Richard Krueger, Geneviève Simonet |