Aller au contenuAller au menuAller à la rechercheAller à la page d'actualités

Soutenance de thèse | Wen SUN - Université Angers

Soutenance de thèse | Wen SUN

  • Partager la page sur les réseaux sociaux
  • Envoyer cette page par mail

    Envoyer par mail


    Séparés par des virgules
  • Imprimer cette page

Soutenance de thèse de Madame Wen SUN

10h40 | Faculté des Sciences | AMPHI L006 | 2, boulevard Lavoisier | ANGERS

Le 29 novembre 2018

Sujet : Optimization Algorithms for Graph Coloring Problems

Directeur de thèse : Monsieur Jin-Kao HAO

RÉSUMÉ

Cette thèse concerne quatre problèmes de coloration de graphes NP-difficiles, à savoir le problème de coloration (GCP), le problème de coloration équitable (ECP), le problème de coloration des sommets pondérés et le problème de sous-graphe critique (k-VCS). Ces problèmes sont largement étudiés dans la littérature, non seulement pour leur difficulté théorique, mais aussi pour leurs applications réelles dans de nombreux domaines. Étant donné qu0ils appartiennent à la classe de problèmes NP-difficiles, il est difficile de les résoudre dans le cas général de manière exacte. Pour cette raison, cette thèse est consacrée au développement d0approches heuristiques pour aborder ces problèmes complexes. Plus précisément, nous développons un algorithme mémétique de réduction (RMA) pour la coloration des graphes, un algorithme de recherche réalisable et irréalisable (FISA) pour la coloration équitable et un réalisable et irréalisable (AFISA) pour le problème de coloration des sommets pondérés et un algorithme de suppression basé sur le retour en arrière (IBR) pour le problème k -VCS. Tous les algorithmes ont été expérimentalement évalués et comparés aux méthodes de l’état de l’art.