Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

A heuristic for the convex recoloring problem in graphs

Full text
Author(s):
Dantas, Ana Paula S. [1] ; de Souza, Cid C. [1] ; Dias, Zanoni [1]
Total Authors: 3
Affiliation:
[1] Univ Campinas Unicamp, Inst Comp, Av Albert Einstein, BR-1251 Campinas, SP - Brazil
Total Affiliations: 1
Document type: Journal article
Source: International Transactions in Operational Research; v. 29, n. 3, p. 1454-1478, MAY 2022.
Web of Science Citations: 0
Abstract

We consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. In this sense, a coloring is said to be convex if every set of all same colored vertices induces a connected subgraph. The Convex Recoloring Problem finds the minimum number of recolored vertices needed to turn a coloring convex. This problem is most commonly studied considering trees due to its origins in Computational Biology, but in this paper, we focus on general graphs. We propose a heuristic based on the Greedy Randomized Adaptive Search Procedure to solve the problem. We present computational experiments for our heuristic and compare it to an Integer Linear Programming (ILP) model from the literature. In these experiments, our heuristic recolored at most one vertex more than the ILP model, and it was also able to give better solutions when the ILP model was unable to find the optimal solution within the time limit. We also introduce a set of benchmark instances for the problem. (AU)

FAPESP's process: 17/16246-0 - Sensitive media analysis through deep learning architectures
Grantee:Sandra Eliza Fontes de Avila
Support Opportunities: Regular Research Grants
FAPESP's process: 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events
Grantee:Anderson de Rezende Rocha
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 18/04760-3 - Convex graph Recoloring
Grantee:Ana Paula dos Santos Dantas
Support Opportunities: Scholarships in Brazil - Master