Title :
Max-Min Ant System for the sum coloring problem
Author :
Mohamed, D.S. ; Elbernoussi, Souad
Author_Institution :
Fac. of Sci. of Rabat, Res. Lab. Math. Comput. & Applic., Mohammed V Univ., Rabat, Morocco
Abstract :
The sum coloring problem (MSCP) is an NP-hard problem derived from the graphs coloring (GCP). The problem (MSCP) consists in minimizing the sum of colors in a graph. Our resolution approach is based on an hybridization of Max-Min Ant System (MMAS) an extension of Ant System and a local heuristic based on an improvement of the maximal independent set algorithm given by F. Glover[4].
Keywords :
computational complexity; graph colouring; minimax techniques; NP-hard problem; graphs coloring; hybridization; max-min ant system; sum coloring problem; Approximation algorithms; Approximation methods; Color; IP networks; Operations research; Optimization; Traveling salesman problems; Max-Min Ant System (MMAS); The sum coloring problem; graph coloring problem; maximal independent set;
Conference_Titel :
Communications, Computing and Control Applications (CCCA), 2011 International Conference on
Conference_Location :
Hammamet
Print_ISBN :
978-1-4244-9795-9
DOI :
10.1109/CCCA.2011.6031417
