Research Topics

Home | Research | Publications | Talks | Vitae

Graph Decomposition and Algorithms
Well-structured Graph Families
Fixed Parameterized Algorithms

Graph Decomposition 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.

Well-structured Graph Families 

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

Fixed parameterized algorithms and kernelization

Different techniques can be considered to solve a difficult problem, say NP-hard. Fixed parameterized algorithms aim at computing an exact solution in time complexity f(k).poly(n), where n is the size of the input and k a fixed parameter (for example, the size of the solution, the treewidth of the graph...) Fixed parameterized complexity has emergered as a growing and important line of research in the past few years. For more details, see the ANR research project AGAPE.


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.