Research TopicsHome | Research | Publications | Talks | Vitae
Graph Decomposition and Algorithms
Well-structured Graph Families
Fixed Parameterized Algorithms
Design of new algorithms for graph decompositions based on partitive or bipartitive families, such as modular decomposition or split decomposition. The algorithmic tools I like to use are for example, partition refinement techniques, Lexicographic Breadth First Search (LexBFS)... I also worked on the classical width parameters and the related tree or branch decompositions. For more details, see the ANR research project GRAAL.
The combinatorial properties of restricted graph families are the basis of efficient algorithms (for example to solve problems that are NP-hard in general). I have particular interest in the recognition problem of graph families such as intersection graphs (interval graphs, chordal graphs, permutation graphs, circle graphs...)
Comparative genomics aims at
finding common structures or patterns in a set of genomes in order to
compute some evolutionnary distance or to help the reconstruction of
evolutionary scenarios. Decomposition trees and related data-structures
helps to compute so called perfect scenarios, that preserves some
common structures. I also collaborated on research projects related to phylogenetic tree or network reconstruction.