A heuristic for the minimum cost chromatic partition problem

¹ Institute of Computing, Universidade Federal Fluminense, Niterói 24210-346, Brazil
² Instituto Federal de Educação, Ciência e Tecnologia Fluminense, Campos dos Goytacazes 28030-130, Brazil

^* Corresponding author: celso@ic.uff.br

Received: 16 January 2019
Accepted: 27 March 2019

Abstract

The graph coloring problem consists in coloring the vertices of a graph G=(V, E) with a minimum number of colors, such as that any two adjacent vertices receive different colors. The minimum cost chromatic partition problem (MCCPP) is an extension of the graph coloring problem in which there are costs associated with the colors and one seeks a vertex coloring minimizing the sum of the costs of the colors used in each vertex. The problem finds applications in VLSI design and in some scheduling problems modeled on interval graphs. We propose a trajectory search heuristic using local search, path-relinking, and perturbations for solving MCCPP and discuss computational results.