CONFERENCE
Rencontres Internationales sur les méthodes de décomposition de graphes
19 au 23 janvier 2015
Les méthodes de décomposition de graphes forment un paradigme puissant pour la théorie des graphes mais aussi pour l’algorithmique combinatoire. Ainsi la théorie des paramètres de largeur de graphes et leurs décompositions associées n’a pas seulement permis des avancées significatives dans la preuve de la conjecture de Wagner sur les mineurs de graphes, elle est de fondement de très nombreux résultats méta-algorithmiques dans le domaine du model checking, de la complexité paramétrée ou la kernelization.
Les objectifs des rencontres sont de faire le point sur les développements récents de ce domaine du point de vue de la théorie des graphes, de l’algorithmique, de la complexité et de la logique. Nous nous intéresserons en particulier, mais pas uniquement, aux décompositions de graphes définis par sous-graphes interdits, aux décompositions de graphes sans mineur topologique, aux conséquences algorithmiques des nouvelles techniques de décomposition…
|
Comité d’organisation & Comité scientifique
Stephan Kreutzer (University of Berlin)
Christophe Paul (CNRS – Université Montpellier)
Nicolas Trotignon (CNRS – ENS Lyon)
Paul Wollan (University of Rome)
Conférenciers
- Aistis Atminas (University of Warwick)
Deciding the Bell number for hereditary graph properties
- Aistis Atminas (University of Warwick)
Deciding the Bell number for hereditary graph properties
- Marthe Bonamy (University of Waterloo)
Recoloring bounded treewidth graphs
- Maria Chudnovsky (Columbia University)
Induced cycles and coloring
- Bruno Courcelle (Université de Bordeaux)
Comparing tree-width and clique-width for degree-constrained graphs
- Pal Grønas Drang (University of Bergen)
Computational Complexity of Threshold Editing
- Zdenek Dvorak (Charles University, Prague)
Strongly sublinear separators and polynomial expansion
- Archontia Giannopoulou (Durham University)
Uniform Kernelization Complexity of Hitting Forbidden Minors
- Georg Gottlob (University of Oxford)
Hypertree Decompositions
- Martin Milanič (University of Primorska)
On the structure of1-perfectly orientable graphs
- Tony Huynh (Sapienza University of Rome)
A(2- E)-Hall’s theorem with an application to space com-plexity
- Felix Joos (Universität Ulm)
The Erdös-Posa property of odd and long cycles throughprescribed vertices
- Mamadou Moustapha Kanté (Université Blaise Pascal)
Upper Bounds on the Size of Obstructions for linear rank-width and linear branch-width of representable matroids
- Eun Jung Kim (Université Paris-Dauphine)
Algorithmic Applications of Tree-Cut Width
- Dan Kral (University of Warwick)
Width Parameters for Matroids
- Stephan Kreutzer (Technical University Berlin)
The Directed Grid Theorem
- O-Joung Kwon (KAIST, South Korea)
Characterizing the linear rank-width of distance-hereditarygraphs via split decompositions
- Chun-Hung Liu (Princeton University)
Erdös-Posa Property for Topological Minors
- Daniel Lokshtanov (Bergen University)
Tree Decompositions and Graph algorithms
- Spyridon Maniatis (University of Athens)
The Parameterized Complexity of Graph Cyclability
- Daniel Marx (Hungarian Academy of Sciences, Hungary)
Optimal parameterized algorithms for planar facility loca-tion problems using Voronoi diagrams and sphere cut de-compositions
- Natasha Morrison (University of Oxford)
Saturation in the Hypercube
- Irene Muzi (University of Rome ”La Sapienza)
Subdivisions in4-connected graphs of large tree-width
- Sang-Il Oum (KAIST, Korea)
Constructive algorithm for path-width and branch-width ofmatroids and rank-width of graphs
- Irena Penev (ENS Lyon)
Amalgams and X-boundedness
- Marcin Pilipczuk (University of Warwick)
Fixed-parameter tractable canonization and isomorphismtest for graphs of bounded treewidth
- Michal Pilipczuk (University of Warsaw)
Kernelization of Dominating Set in sparse graph classes
- Jean-Florent Raymond (Université de Montpellier)
Multigraphs without large bonds are wqo by contraction
- Ignasi Sau (Université de Montpellier)
FPT algorithm for a generalized cut problem and some applications
- Paul Seymour (Princeton University)
Colouring graphs with no odd holes, and other stories
- Jan Arne Telle (University of Bergen)
Solving #SATand MaxSAT by dynamic programming
- Stéphan Thomassé (ENS Lyon)
Induced Cycles Modulo 3
- Ioan Todinca (Université d’Orléans)
Large Induced Subgraphs Via Triangulations and CMSO
|
