Efficient enumeration algorithms for minimal graph completions and deletions

Algorithmes d'énumération efficaces pour les complétions et délétions minimales de graphes 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.La thèse se décompose de la manière suivante.D'abord, les principaux algorithmes d'énumération existants sont présentés.Puis on s'intéresse à la propriété split, pour laquelle on donne un algorithme à délai polynomial en espace polynomial pour l'énumération des complétions minimales et délétions minimales (sous-graphes maximaux non induits).On s'intéresse ensuite à une technique d'énumération existante appelée Flashlight Search et on montre qu'elle ne peut être utilisée pour énumérer efficacement les sous-graphes maximaux dans n'importe quelle classe.Après cela, la récente technique de Proximity Search est appliquée à l'énumération des sous-graphes maximaux induits dans la classe des cographes, des sous-graphes threshold maximaux induits et des délétions minimales en graphe threshold.Nous obtenons ainsi des algorithmes à délai polynomial en espace exponentiel.Cette technique est aussi appliquée avec succès à l'énumération des complétions minimales en graphe cordal, pour lesquelles l'existence d'un algorithme à délai polynomial était un problème ouvert.Enfin, une généralisation de la technique de Proximity Search est proposée, et une nouvelle technique fondée sur le Proximity Search pour des algorithmes à délai polynomial en espace polynomial est introduite.Nous appliquons cette technique à la plupart des problèmes résolus dans cette thèse via Proximity Search, ce qui réduit leur complexité en espace.