AlGCo : algorithmes, graphes et combinatoire

Responsable : Mickael Montassier

Département Informatique - LIRMM


Accueil | Membres | Projets | Visiteurs | Publications | Séminaire


English version here

Accueil

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, algorithmes exacts, complexité paramétrée et kernelization
    (projet régional Kernel 2012/2015, voir ici - projet ANR Agape 2009/2013, voir ici - 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.

    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.

    La génération croissante de grandes masses de données est un phénomème commun à de nombreuses discplines scientifiques (biologie, physique, sciences de l’environnement…) L'exploitation de ces données requière des traitements informatiques systématiques allant du stockage, de la fouille des données à l'optimisation et donc l'algorithmique. Les techniques de pré-traitement sont depuis toujours à la base des méthodes heuristiques. Ce n'est pourtant qu'aux alentours de 2005 que la théorie de la kernelisation offre un cadre formel pour leur étude. Jusqu'ici essentiellement appliquée à des problèmes issus de la théorie des graphes, nous étendrons le champs de la kernelisation à d'autres domaines d'applications à l'interface de l'informatique. Nos objectifs seront aussi de compléter cette théorie du point vue de la complexité algorithmique (bornes, limites).

  • Graphes dans les structures topologiques, graphes plongés et leurs structures orientées
    (projet ANR GATO 2016/2020, voir ici - projet ANR Egos 2012/2015, voir ici - 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..

    Dans le plan, de nombreuses familles de graphes ont des structures orientées, c'est à dire des orientations et colorations des arêtes du graphe, satisfaisant une certaine propriété locale. Par exemple: les graphes planaires bipartis 2-connexes admettent des 2-orientations, les graphes planaires 3-connexes admettent des forêts de Schnyder (Schnyder woods), les triangulations planaires 4-connexes admettent des structures transversales. Ces structures sont en bijection avec plusieurs objets combinatoires comme les sysèmes de contacts de polygones, les triangulations TD-Delaunay, ou les mots de Dyck. Elles s'avèrent aussi avoir diverses applications en informatique comme des codage compacts, des dessins de graphes, des générations de graphes (graph spanners), etc. Ce projet à pour but de généraliser ces structures orientées à des surfaces de genre supérieur et à des objets de dimensions supérieures.

  • Matroïdes et matroïdes orientés, théorie mathématique et applications interdisciplinaires
    (projet régional Omsmo 2016/2019, voir ici - projet ANR Teomatro 2010/2014, voir ici)

    La théorie des matroïdes et matroïdes orientés généralise la théorie des graphes en tant qu'espaces de cycles, constitue une abstraction combinatoire de l'algèbre linéaire, et fournit un langage approprié pour les relations d'icidence et de convexité dans divers objets géométriques ou topologiques : configurations de points, polytopes, arrangements de droites, de pseudodroites, d'hyperplans, de pseudohyperlans, de pseudosphères... Des notions combinatoires variées trouvent là un cadre théorique naturel (dualité des graphes, dualité de la programmation linéaire, polynôme de Tutte, etc.).

    Une application développée actuellement concerne le codage combinatoire de formes à l'aide de ces structures. Le but est de développer une théorie et un outil informatique pour l'analyse/comparaison/classification de formes de modèles 2D/3D, pour applications dans diverses disciplines : médecine, anthropologie, paléontologie, imagerie...

Et quelques mots clés supplémentaires : algorithmes de modifications de graphes, algorithmes dynamiques, représentations compactes de classes de graphes, optimisation dans les graphes orientés, coloration de graphes...

Contacts : M. Montassier

contact toilemestre AlGCo