Nos tutelles

CNRS

Nos partenaires


Accueil > Publications > Thèses > Archives Thèses > Thèses 2013 - 2014

MARY Arnaud


Énumération des dominants minimaux d’un graphe

Vendredi 29 novembre 2013 - 14 h 00 - Amphi Bruno Garcia - ISIMA

Un dominant d’un graphe G, est un sous-ensemble D de sommets de G tel que tout sommet à l’extérieur de D, possède au moins un voisin dans D. Un dominant est dit minimal, s’il ne contient aucun autre dominant. Dans cette thèse, nous nous proposons d’étudier le problème d’énumération des dominants minimaux d’un graphe, c’est à dire, le problème consistant à lister tous les dominants minimaux d’un graphe donné. Nous montrons notamment que ce problème est équivalent au fameux problème d’énumération des transversaux minimaux d’un hypergraphe. Nous présentons des méthodes générales permettant d’obtenir des algorithmes d’énumérations, et nous les appliquons pour énumérer efficacement les dominants minimaux dans de nombreuses classes de graphes. Enfin, nous considérons l’énumération d’autre objets liés à la domination dans les graphes tels que les dominants connexes, les dominants totaux ou encore les ensembles arête-dominants.

Jury :
Dieter KRATSCH - Professeur, Université de Lorraine, Metz - Rapporteur
Arnaud DURAND - Professeur, Université Paris 7 - Rapporteur
Takeaki UNO - Professeur, National Institute of Informatics, Japan - Examinateur
Stéphan THOMASSÉ - Professeur, ENS Lyon - Examinateur
Jean-Marc PETIT - Professeur, INSA Lyon - Examinateur Codirecteur
Vincent LIMOUZY - MCF, UBP Clermont-Ferrand - Codirecteur
Mamadou M. KANTÉ - MCF, UBP Clermont-Ferrand - Codirecteur
Lhouari NOURINE - Professeur, UBP Clermont-Ferrand – Codirecteur.