Program
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.