Un algorithme constructif efficace pour le problème de coloration de graphe

Le problème de coloration de graphe consiste à assigner à chaque sommet une couleur de sorte que deux sommets adjacents n'aient pas la même couleur tout en utilisant le nombre minimal de couleur. C'est l'un des problèmes les plus étudiés en optimisation combinatoire en raison de ses multiples applications (la planification des horaires, l'allocation des ressources, etc.) et de la complexité de sa résolution. De nombreuses méthodes de résolutions ont été proposées pour résoudre le problème de coloration de graphe. Elles peuvent être réparties en trois catégories : les méthodes exactes dont le temps de calcul croît exponentiellement avec le nombre de sommets du graphe, les méthodes constructives qui donnent rapidement une approximation de la solution optimale du problème, et les métaheuristiques qui fournissent de meilleurs résultats mais au prix d'algorithmes plus complexes et plus gourmands en temps de calcul. Dans le présent mémoire, nous avons conçu un algorithme constructif d'ordre polynomial qui colore le graphe, une couleur à la fois, en priorisant les voisins des voisins des nœuds déjà colorés. Les résultats des tests effectués sur les graphes classiques du banc d'essai démontrent l'efficacité de l'algorithme proposé qui, pour un temps raisonnable, donne des résultats similaires que TABUCOL, la métaheuristique la plus connue.