AlGCo : algorithmes, graphes et combinatoire

Cette équipe est née fin 2008 en remaniement de l'équipe VAG, le site obsolète de l'équipe VAG est ici.
Le domaine commun de l'équipe est la théorie des graphes, et plus généralement l'étude de problèmes algorithmiques et de structures combinatoires.

Les thèmes majeurs de l'équipe sont :

• Décompositions de graphes (projet ANR Graal 2006/2009, voir ici)
  Les méthode de décompositions de graphes (arborescente, en branches, modulaire, en splits...), et leurs éventuels paramètres associés (tree-width, branch-width, rank-width...) sont importantes pour plusieurs raisons. D'abord, décomposer un graphe est souvent une étape préliminaire dans la résolution d'un problème donné. Ensuite, du point de vue algorithmique, une décomposition permet d'envisager des algorithmes traitant séparément les composantes et la structure qui les relie. Notamment, un paramètre associé peut mesurer la qualité de la décomposition, permettant d'obtenir des algorithmes de faibles complexités lorsque ce paramètre est borné. Enfin, les décompositions reposent souvent sur (ou bien font ressortir) des propriétés combinatoires intéressantes, qui peuvent s'étendre à des structures plus générales.
  
  
• Algorithmes exacts et FPT (projet ANR Agape 2009/2012, voir ici)
  L'algorithmique à paramètre fixé, et la complexité paramétrée FPT (fixed parameter tractability) associée, se placent dans l'approche des algorithmes exponentiels exacts en proposant une analyse de la complexité plus fine que l'approche classique, en prenant en compte non seulement la taille des données d'entrée mais également un paramètre associé au problème (comme par exemple avec certains paramètres de décompositions ci-dessus). Idéalement, on cherche à trouver un paramètre k tel que la complexité du problème de taille n soit du type O(f(k).n) pour une certaine fonction f.
  
  
• Graphes dans les structures topologiques (projet ANR Gratos 2009/2012, voir ici)
  Il s'agit d'étudier des interactions entre la théorie des graphes et des structures, problèmes ou modèles de nature topologique : des graphes plongés sur des surfaces (graphes planaires notamment, qui représentent le cas de base de nombreux problèmes algorithmiques ou combinatoires), des graphes définis par intersection d'objets géométriques, des invariants de graphes qui caractérisent leurs propriétés topologiques, des liens avec des structures topologiques plus générales (complexes simpliciaux, matroïdes et leur dualité, polytopes...), etc..

Nous nous intéressons aussi, de façon plus individuelle, en liaison ou non avec les thèmes précedents, aux sujets suivants :

• optimisation dans les graphes orientés
• coloration de graphes
• codages, algorithmes dynamiques, représentations compactes de classes de graphes
• modèles d'intersections géométriques
• théorie des hypergraphes
• théorie des matroïdes, matroïdes orientés et arrangements d'hyperplans

Contacts : C. Paul