Cette thèse porte sur la théorie des graphes et plus particulièrement les algorithmes d'énumération de sous-graphes ou sur-graphes. Le problème auquel on s'intéresse est le suivant : étant donné un graphe quelconque G et une propriété de graphes P, peut-on trouver un algorithme efficace qui génère une et une seule fois tous les sous-graphes maximaux pour l'inclusion (induits ou non) de G qui vérifient la propriété P ? De même, on s'intéresse aussi aux sur-graphes de G minimaux pour l'inclusion — appelés complétions minimales de G — qui vérifient P.
Des algorithmes efficaces, à délai polynomial en espace polynomial, sont obtenus pour certains de ces problèmes lorsque P décrit la classe des graphes split, des cographes, des graphes threshold et des graphes cordaux.

Jury :
Fatiha Bendali - Université Clermont Auvergne - Examinatrice
Marthe Bonamy - CNRS, Université de Bordeaux - Examinatrice
Nofar Carmeli - Inria, Université de Montpellier - Examinatrice
Roberto Grossi - Università di Pisa - Rapporteur
Christian Laforest - Université Clermont Auvergne - Examinateur
Vincent Limouzy - Université Clermont Auvergne - Directeur de thèse
Ioan Todinca - Université d'Orléans - Rapporteur
Nicolas Trotignon - CNRS, ENS de Lyon - Examinateur.