Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

A heuristic for the convex recoloring problem in graphs

Texto completo
Autor(es):
Dantas, Ana Paula S. [1] ; de Souza, Cid C. [1] ; Dias, Zanoni [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Campinas Unicamp, Inst Comp, Av Albert Einstein, BR-1251 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: International Transactions in Operational Research; NOV 2020.
Citações Web of Science: 0
Resumo

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)

Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade
Beneficiário:Anderson de Rezende Rocha
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo
Beneficiário:Sandra Eliza Fontes de Avila
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 18/04760-3 - Recoloração convexa de grafos
Beneficiário:Ana Paula dos Santos Dantas
Linha de fomento: Bolsas no Brasil - Mestrado