31. WG 2005: Metz, France

Invited Lectures

• Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, Francesco Scarcello:
  Hypertree Decompositions: Structure, Algorithms, and Applications. 1-15
  
• Mathilde Bouvel, Vladimir Grebinski, Gregory Kucherov:
  Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey. 16-27
  

Regular Papers

• Divesh Aggarwal, Shashank K. Mehta, Jitender S. Deogun:
  Domination Search on Graphs with Low Dominating-Target-Number. 28-37
  
• Christophe Crespelle, Christophe Paul:
  Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs. 38-48
  
• Sang-il Oum:
  Approximating Rank-Width and Clique-Width Quickly. 49-58
  
• Omer Giménez, Petr Hlinený, Marc Noy:
  Computing the Tutte Polynomial on Graphs of Bounded Clique-Width. 59-68
  
• Frank Gurski, Egon Wanke:
  Minimizing NLC-Width is NP-Complete. 69-80
  
• Frédéric Havet, Jean-Sébastien Sereni:
  Channel Assignment and Improper Choosability of Graphs. 81-90
  
• Daniel Meister:
  Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time. 91-102
  
• Mathieu Liedloff, Ton Kloks, Jiping Liu, Sheng-Lung Peng:
  Roman Domination over Some Graph Classes. 103-114
  
• Jirí Fiala, Daniël Paulusma, Jan Arne Telle:
  Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms. 115-126
  
• Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, L. Shankar Ram:
  Network Discovery and Verification. 127-138
  
• Emeric Gioan:
  Complete Graph Drawings Up to Triangle Mutations. 139-150
  
• Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Chenyu Yan:
  Collective Tree 1-Spanners for Interval Graphs. 151-162
  
• Van Bang Le, Raffaele Mosca, Haiko Müller:
  On Stable Cutsets in Claw-Free Graphs and Planar Graphs. 163-174
  
• Prosenjit Bose, Vida Dujmovic, David R. Wood:
  Induced Subgraphs of Bounded Degree and Bounded Treewidth. 175-186
  
• Pinar Heggernes, Daniel Lokshtanov:
  Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time. 187-198
  
• Anne Berry, Richard Krueger, Geneviève Simonet:
  Ultimate Generalizations of LexBFS and LEX M. 199-213
  
• Stavros D. Nikolopoulos, Leonidas Palios:
  Adding an Edge in a Cograph. 214-226
  
• Michael Gatto, Riko Jacob, Leon Peeters, Anita Schöbel:
  The Computational Complexity of Delay Management. 227-238
  
• Daniel Gonçalves, Mickaël Montassier:
  Acyclic Choosability of Graphs with Small Maximum Degree. 239-248
  
• Shin-Ichi Nakano, Takeaki Uno:
  Generating Colored Trees. 249-260
  
• Ephraim Korach, Margarita Razgon:
  Optimal Hypergraph Tree-Realization. 261-270
  
• Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stéphane Vialette:
  Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints. 271-282
  
• Peter Damaschke:
  On the Fixed-Parameter Enumerability of Cluster Editing. 283-294
  
• Manuel Bodirsky, Daniel Král:
  Locally Consistent Constraint Satisfaction Problems with Binary Constraints. 295-306
  
• Robert Elsässer, Thomas Sauerwald:
  On Randomized Broadcasting in Star Graphs. 307-318
  
• Torsten Tholey:
  Finding Disjoint Paths on Directed Acyclic Graphs. 319-330
  
• Eric Angel, Evripidis Bampis, Laurent Gourvès:
  Approximation Algorithms for the Bi-criteria Weighted max-cut Problem. 331-340
  
• Akihisa Kako, Takao Ono, Tomio Hirata, Magnús M. Halldórsson:
  Approximation Algorithms for the Weighted Independent Set Problem. 341-350
  
• Erik Jan van Leeuwen:
  Approximation Algorithms for Unit Disk Graphs. 351-361
  
• Pascal Berthomé, Sylvain Lebresne, Kim Nguyen:
  Computation of Chromatic Polynomials Using Triangulations and Clique Trees. 362-373
  
• Fedor V. Fomin, Frédéric Mazoit, Ioan Todinca:
  Computing Branchwidth Via Efficient Triangulations and Blocks. 374-384
  
• Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith:
  Algorithms Based on the Treewidth of Sparse Graphs. 385-396
  
• Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier:
  Extending the Tractability Border for Closest Leaf Powers. 397-408
  
• Joachim Giesen, Dieter Mitsche:
  Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model. 409-420
  
• Ross M. McConnell, Fabien de Montgolfier:
  Algebraic Operations on PQ Trees and Modular Decomposition Trees. 421-432
  
• Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara:
  Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs. 433-444
  
• Anne Berry, Alain Sigayret, Jeremy Spinrad:
  Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny. 445-455
  
• Stavros D. Nikolopoulos, Leonidas Palios:
  Recognizing HHDS-Free Graphs. 456-467
  

Last update Sat May 25 19:27:35 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page