Title :
A hybrid algorithm for the sum coloring problem
Author :
Douiri, Sidi Mohamed ; Bernoussi, S.E.
Author_Institution :
Fac. of Sci. Rabat, Res. Lab. Math., Comput. & Applic., Univ. Mohammed V - Agdal Rabat, Rabat, Morocco
Abstract :
In this work, we study the sum coloring graphs problem (MSCP), which is a variant of the graph coloring one. The purpose of (MSCP) is to affect natural numbers (colors) at each vertex, and to minimize the sum of colors. We present afterwards an hybrid algorithm based on heuristic given by the improved algorithm of F. Glover [1] and metaheuristic ant colony optimization (ACO).
Keywords :
computational complexity; graph colouring; optimisation; ACO; F. Glover algorithm; MSCP; NP-hard problems; hybrid algorithm; metaheuristic ant colony optimization algorithm; sum coloring graphs problem; Ant colony optimization; Approximation algorithms; Approximation methods; Color; Heuristic algorithms; IP networks; Optimization; The sum coloring problem; ant colony optimization; maximal independent set;
Conference_Titel :
Multimedia Computing and Systems (ICMCS), 2011 International Conference on
Conference_Location :
Ouarzazate
Print_ISBN :
978-1-61284-730-6
DOI :
10.1109/ICMCS.2011.5945684
