Paper Info
Title
A GRASP for the Convex Recoloring Problem in Graphs.
Abstract
In this paper, we consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. The Convex Recoloring Problem finds the minimum number of recolored vertices needed to turn a coloring convex, that is, every set formed by all the vertices with the same color induces a connected subgraph. The problem is most commonly studied considering trees due to its origins in the study of phylogenetic trees, but in this paper, we focus on general graphs and propose a GRASP heuristic to solve the problem. We present computational experiments for our heuristic and compare it to an Integer Linear Programming model from the literature. In these experiments, the GRASP algorithm recolored a similar number of vertices than the model from the literature, and used considerably less time. We also introduce a set of benchmark instances for the problem.
Year
DOI
Venue
2019
10.1016/j.entcs.2019.08.034
Electronic Notes in Theoretical Computer Science
Keywords
Field
DocType
Convex Recoloring,GRASP,Combinatorial Optimization
Discrete mathematics,Graph,Heuristic,GRASP,Vertex (geometry),Computer science,Integer linear programming model,Regular polygon,Vertex connectivity
Journal
Volume
ISSN
Citations 
346
1571-0661
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Ana Paula dos Santos Dantas100.34
Cid Carvalho de Souza2786.91
Zanoni Dias326244.40