Volume 54, Number 3, May-June 2020
|Page(s)||845 - 871|
|Published online||20 March 2020|
A heuristic for the minimum cost chromatic partition problem
Institute of Computing, Universidade Federal Fluminense, Niterói 24210-346, Brazil
2 Instituto Federal de Educação, Ciência e Tecnologia Fluminense, Campos dos Goytacazes 28030-130, Brazil
* Corresponding author: firstname.lastname@example.org
Accepted: 27 March 2019
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.
Mathematics Subject Classification: 90C27 / 68R10
Key words: Minimum cost chromatic partition problem / graph coloring problem / metaheuristics / trajectory search heuristic / path-relinking
© EDP Sciences, ROADEF, SMAI 2020
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.