Research Topics

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)... For more details, see the ANR research project GRAAL. Main results are: 

• Simple, linear-time modular decomposition. With M. Tedder (U. of Toronto), D. Corneil (U. of Toronto) and M. Habib (LIAFA, U. de Paris 7). Presented at ICALP 2008.

• Dynamic distance hereditary graphs using split decomposition. With E. Gioan (CNRS, LIRMM). Presented at ISAAC 2007.

• LexBFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. With M. Habib, R. McConnell and L. Viennot. Presented at STACS 1998.

• New Tools and Simpler Algorithms for Branchwidth. With J.A. Telle (U. of Bergen). Presented at ESA 2005. 

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...);I also studied compact representation of graphs for adjacency, distance... queries. 

• A simple linear time LexBFS cograph recognition algorithm. With A. Bretscher (U. of Toronto), D. Corneil (U. of Toronto) and M. Habib (LIAFA, U. de Paris 7). Presented at WG 2003.

• Optimal Distance Labeling for Interval and Circular-Arc Graphs. With C. Gavoille (LaBRI, U. de Bordeaux 1). Presented at ESA 2003.

Fixed parameterized algorithms

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. The main results I co-authored in this context are:

• Interval graph completion with few edges. With P. Heggernes, J.A. Telle and Y. Villanger (University of Bergen). Presented at STOC 2007

• Polynomial kernels for 3-leaf power graph modification problems. With S. Bessy and A. Perez (LIRMM). Submitted

Bioinformatics

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. For more details, see:

• Sorting by Intervals with Common Intervals is not Always Difficult. WithS. Bérard (INRA), A. Bergeron (U. dy Québec à Montréal), C. Chauve (U. dy Québec à Montréal) . Presented at WABI 2005.

I also collaborated on  research projects related to phylogenetic tree or network reconstruction. See for example:

• Linear time 3-approximation for MAST problem. With V. Berry (LIRMM, U. de Montpellier 2), S. Guillemot (LIRMM, U. de Montpellier 2) and F. Nicolas (LIRMM, U. de Montpellier 2). Presented at COCOON 2005.