DocumentCode
3467683
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
fYear
2011
fDate
3-5 March 2011
Firstpage
1
Lastpage
4
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Communications, Computing and Control Applications (CCCA), 2011 International Conference on
Conference_Location
Hammamet
Print_ISBN
978-1-4244-9795-9
Type
conf
DOI
10.1109/CCCA.2011.6031417
Filename
6031417
Link To Document