31st International Workshop on Graph-Theoretic
Concepts in Computer Science

Wednesday, June 22nd
20.00 Welcome Reception
The registration desk is open from 16.00 till 21.00
Payments are to be made on Thursday, June 23, from 8.00 till 12.00
Thursday, June 23rd
8.50 Opening
9.00 Invited Talk: Georg Gottlob: Hypertree Decompositions: Structure, Algorithms and Applications
9.50 Divesh Aggarwal, Shashank K. Mehta, Jitender S. Deogun: Domination Search on Graphs with Low Dominating-Target Number
10.15 Christophe Crespelle, Christophe Paul: Fully dynamic algorithm for modular decomposition and recognition of permutation graphs
10.40 Coffee
11.00 Sang-il Oum: Approximating Rank-width and Clique-width Quickly
11.25 Omer Gimenez, Petr Hlineny, Marc Noy: Computing the Tutte Polynomial on Graphs of Bounded Clique-Width
11.50 Frank Gurski, Egon Wanke: Minimizing NLC-width is NP-complete
12.15 Frédéric Havet, Jean-Sébastien Sereni: Channel assignment and improper choosability of graphs
12.40 Lunch
14.15 Daniel Meister: Computing treewidth and minimum fill-in for permutation graphs in linear time
14.40 Mathieu Liedloff, Ton Kloks, Jiping Liu, Sheng-Lung Peng: Roman domination over some graphs classes
15.05 Jiri Fiala, Daniel Paulusma, Jan Arne Telle: Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms
15.30 Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, L. Shankar Ram: Network Discovery and Verification
15.55 Coffee
16.15 Emeric Gioan: Complete graph drawings up to triangle mutations
16.40 Derek G. Corneil, Feodor F. Dragan, Ekkehard Koehler, Chenyu Yan: Collective tree 1-spanners for interval graphs
17.05 Van Bang Le, Raffaele Mosca, Haiko Müller: On stable cutsets in claw-free graphs and planar graphs
18.00 PC Meeting
20.00 Dinner in the Restaurant "A la ville de Lyon" §
Friday, June 24th
9.00 Prosenjit Bose, Vida Dujmovic, David R. Wood: Induced Subgraphs of Bounded Degree and Bounded Treewidth
9.25 Pinar Heggernes, Daniel Lokshtanov: Optimal broadcast domination of arbitrary graphs in polynomial time
9.50 A. Berry, R. Krueger, G. Simonet: Ultimate generalizations of LexBFS and LEX M
10.15 Stavros D. Nikolopoulos, Leonidas Palios: Adding an Edge in a Cograph
10.40 Coffee
11.00 Michael Gatto, Riko Jacob, Leon Peeters, Anita Schöbel: The Computational Complexity of Delay Management
11.25 Daniel Gonçalves, Mickaël Montassier: Acyclic choosability of graphs with small maximum degree
11.50 Shin-ichi Nakano, Takeaki Uno: Generating Colored Trees
12.15 Ephraim Korach, Margarita Razgon: Optimal hypergraph tree-realization
12.40 Lunch
14.15 Invited Talk: Gregory Kucherov: Combinatorial search on graphs motivated by bioinformatics applications: a case study and generalizations
15.05 Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stéphane Vialette: Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
15.30 Peter Damaschke: On the Fixed-Parameter Enumerability of Cluster Editing
15.55 Coffee
16.15 Manuel Bodirsky, Daniel Kral: Locally Consistent Constraint Satisfaction Problems with Binary Constraints
16.40 Robert Elsaesser, Thomas Sauerwald: On Randomized Broadcasting in Star Graphs
17.05 Torsten Tholey: Finding Disjoint Paths on Directed Acyclic Graphs
19.00 Dinner in the Restaurant "Les Amis de Saint Louis" §
21.00 Guided Tour
Saturday, June 25th
9.00 Eric Angel, Evripidis Bampis, Laurent Gourves: Approximation algorithms for the bi-criteria weighted max cut problem
9.25 Akihisa Kako, Takao Ono, Tomio Hirata, Magnus M. Halldorsson: Approximation Algorithms for the Weighted Independent Set Problem
9.50 Erik Jan van Leeuwen: Approximation Algorithms for Unit Disk Graphs
10.15 P. Berthomé, S. Lebresne, K. Nguyen: Computation of chromatic polynomials using triangulations and clique trees
10.40 Coffee
11.00 Fedor Fomin, Frédéric Mazoit, Ioan Todinca: Computing branchwidth via efficient triangulations and blocks
11.25 Joachim Kneis, Daniel Moelle, Stefan Richter, Peter Rossmanith: Algorithms Based on Treewidth of Sparse Graphs
11.50 Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier: Extending the tractability border for Closest Leaf Powers
12.15 Joachim Giesen, Dieter Mitsche: Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model
12.40 Lunch
14.15 Ross M. McConnell, Fabien de Montgolfier: Algebraic Operations on PQ Trees and Modular Decomposition Trees
14.40 Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara: Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs
15.05 Anne Berry, Alain Sigayret, Jeremy Spinrad: Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny
15.30 Stavros D. Nikolopoulos, Leonidas Palios: Recognizing HHDS-free Graphs
15.55 Closing
16.05 End of workshop

§: There is a limited number of available places in each of the restaurants. If necessary we shall reserve a dinner in other restaurants for a part of the participants.

LITA University of Metz