A memetic algorithm for the Minimum Sum Coloring Problem. Jin, Y., Hao, J., K., & Hamiez, J., P. Computers and Operations Research, 43:318-327, Elsevier, 3, 2014.
A memetic algorithm for the Minimum Sum Coloring Problem [pdf]Paper  A memetic algorithm for the Minimum Sum Coloring Problem [link]Website  abstract   bibtex   
Given an undirected graph G, the Minimum Sum Coloring Problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 15 instances. ?? 2013 Elsevier Ltd. All rights reserved.

Downloads: 0