Nos tutelles

CNRS

Nos partenaires


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

PHAN Raksmey


Méthodes exactes et approchées par partition en cliques de graphes

Jeudi 28 novembre 2013 - 14 h 00 - Amphi Bruno Garcia ISIMA

Nous nous intéressons à la résolution exacte et approchée de deux problèmes de graphes. Dans un soucis de compromis entre la durée d’exécution et la qualité des solutions, nous proposons une nouvelle approche par partition en cliques qui a pour but (1) de résoudre de manière rapide des problèmes exacts et (2) de garantir la qualité des résultats trouvés par des algorithmes d’approximation. Nous avons combiné notre approche avec des techniques de filtrage et une heuristique de liste. Afin de compléter ces travaux théoriques, nous avons implémenté et comparé nos algorithmes avec ceux existant dans la littérature.

Dans un premier temps, nous avons traité le problème de l’indépendant dominant de taille minimum. Nous résolvons de manière exacte ce problème et démontrons qu’il existe des graphes particuliers dans lesquels le problème est $2$-approximable. Dans un second temps nous résolvons par un algorithme exact et un algorithme d’approximation le problème du vertex cover et du vertex cover connexe. Puis à la fin de cette thèse, nous avons étendu nos travaux aux problèmes proches, dans des graphes comprenant des conflits entre les sommets.

Mots clés :
exact, approximation, heuristique gloutonne, indépendant dominant, vertex cover, conflits.

Jury  :
Johanne COHEN - Chargée de Recherche au LRI - Paris - Rapporteur
Pascal BERTHOMÉ - Professeur à l’Université d’Orléans - Rapporteur
François DELBOT - Maître de conférence à l’Université Paris-Ouest-Nanterre - Paris - Examinateur
Alain QUILLIOT - Professeur à l’Université Blaise Pascal - Clermont Ferrand - Examinateur
Christian LAFOREST - Professeur à l’Université Blaise Pascal - Clermont-Ferrand - Directeur de thèse