Schedule

List of participants

Sponsors

Abstracts

Photo

Videos

---

CONFERENCE

International Workshop on Graph Decomposition 

January 19 - 23, 2015

Graph Decomposition methods offer a powerful paradigm to graph theorists but also to combinatorial algorithmic designers. A milestone example is the theory of width parameters and the associated decompositions at the origin of major steps in the proof of Wagner’s conjecture on graph minors. This theory also provided the foundations of new algorithmic paradigm and led to major meta-algorithmic results in the context of model checking, parameterized complexity or kernelization.

The goals of the workshop are to discuss and exchange on recent developments on graph decomposition methods from the view points of graph theory, algorithmic theory, complexity and logics. Among the thematics of the workshop we may find new decomposition for graph classes defined by forbidden induced subgraphs, graph decompositions for topological minor free graphs, algorithmic consequences of new decomposition techniques…

Scientific & Organizing Committee

Stephan Kreutzer (University of Berlin)
Christophe Paul (Université Montpellier II)
Nicolas Trotignon (ENS Lyon)
Paul Wollan (University of Rome)

Speakers

• 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 (University of 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