# A memetic algorithm for the minimum sum coloring problem

arXiv: https://arxiv.org/abs/1304.2641 · HTML: https://mlsanity.com/paper/1304.2641/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2013.

## Built on by (most cited first, 2 of 2)

- [A deep learning guided memetic framework for graph coloring problems](https://mlsanity.com/paper/2109.05948/) (2021)
- [A massively parallel evolutionary algorithm for the partial Latin square extension problem](https://mlsanity.com/paper/2103.10453/) (2021)

## Abstract (arXiv)

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 17 instances. We also provide upper bounds for 18 additional instances for the first time.