Workshop on Graph Decomposition: Theoretical, Algorithmic and Logical Aspects

April 7-11, 2008

CIRM, Luminy, Marseille (France)

Organized by the French ANR project "Décomposition de graphes et algorithmes"

Monday 7th:

10h15: Openning session
10h30: S.I Oum "Finding branch-decomposition and rank-decompositions"
11h30: V. Jelinek (Prague) "The rankwidth of the grid"

16h30: H. Bodlaender "Algorithms for finding tree decompositions..."
17h30: Y. Villanger (U. Bergen) "Computing treewidth with help of firefighters"
18h00: J. Daligault (LIRMM) "The well quasi-order of relabel functions"
18h30: J.A. Telle (U. Bergen) "H-join graphs and rankwidth"

Tuesday 8th:

9h30: M. Fellows "What about trees ? ..."
10h30: M. Tedder (U. of Toronto) "Linear time modular decomposition"
11h00: M. Rao (LIRMM) "Representing partitive crossing families ..."
11h30: P. Ille (IML) "Hypercritical graphs and their applications"

17h00: D. Thilikos "Bidimensionality, decompositions and subexponential parameterized algorithms"
18h00: D. Johanssen (Max-Planck-Institut) "A direct decomposition of 3-connected planar graphs"
18h30: C. de Figueiredo (U.F. Rio de Janero) "2K2 vertex-set partition into nonempty parts

Wednesday 9th:

9h30: D. Kratsch "Fast exponential algorithms..."
10h30: F. Havet (MASCOTTE) "Decomposing graphs into dense cliques"
11h00: D. Coudert (MASCOTTE) "On the process number of (di)graphs"
11h30: P. Jegou (LSIS) "Hypertree decomposition vs tree decomposition for solving constraint networks"
12h00: Z. Miklos (U. Oxford) "Understanding tractable decomposition for constraint satisfactions"

Thursday 10th:

9h30: J. Makowsky "Connection matrices of numeric graph invariants"
10h30: P. Skums (Minks) "Operator decomposition of graphs and their applications"
11h00: L. Lyaudet (LIFO) "Graph covering and algebraic complexity"
11h30: E. Gioan (LIRMM) "TBA"

17h00: F. Fomin "Parameterized algorithms for partial covering problems"
18h00: R. Encisco(U. of Central Florida) "Parameterized complexity of the secure sets problem"
18h30: S. Guillemot (LIFL) "Homogeneous path systems"

Friday 11th:

9h30: B. Courcelle (LaBRI) "Labelling schemes for solving FO and MSO queries..."
10h30: B. Lévêque (EP. Lausanne)"Characterizing path graphs by forbidden induced subgraphs"
11h00: S. Burkel () "The inductive kernel of graphs"
11h30: G. Even (Tel-Aviv Univ.) "Online randomized preemptive algorithms for disjoint paths in series-parallel graphs"