<  Retour au portail Polytechnique Montréal

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

Mouhamed Mourchid Adio Adegbindin

Mémoire de maîtrise (2013)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (301kB)
Afficher le résumé
Cacher le résumé

Résumé

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.

Abstract

The Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. Due to its numerous practical applications (scheduling, resource allocation, etc.) and computational complexity, the VCP is one of the most studied problems in combinatorial optimization. Several methods have been proposed to solve the VCP. They can be classified in three families: exact approaches whose running time increases exponentially with the size of the graph, greedy algorithms which approximate the optimal solution in a short time and metaheuristic methods which are the best performing algorithms, but are more complex and time consuming. In this work, we design a polynomial incremental algorithm which colors the graph, one class at a time by favouring the neighbours of neighbours of already colored vertices. Computational results on the set of DIMACS benchmark instances demonstrate the efficiency of the proposed algorithm which gives the same results as the popular metaheuristic TABUCOL in reasonable running time.

Département: Département de génie informatique et génie logiciel
Programme: Génie informatique
Directeurs ou directrices: Martine Bellaïche
URL de PolyPublie: https://publications.polymtl.ca/1136/
Université/École: École Polytechnique de Montréal
Date du dépôt: 22 oct. 2013 13:45
Dernière modification: 08 nov. 2022 11:52
Citer en APA 7: Adegbindin, M. M. A. (2013). Un algorithme constructif efficace pour le problème de coloration de graphe [Mémoire de maîtrise, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/1136/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document