Heurísticas para determinação da distância de inversões entre triangulações
Planejamento da expansão de sistemas de transmissão de energia elétrica usando o m...
Controle preditivo de bombas hidráulicas em sistemas de distribuição de água por o...
| Texto completo | |
| Autor(es): |
dos Santos Dantasa, Ana Paula
;
de Souzaa, Cid Carvalho
;
Dias, Zanoni
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30. |
| Resumo | |
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. (AU) | |
| 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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 18/04760-3 - Recoloração convexa de grafos |
| Beneficiário: | Ana Paula dos Santos Dantas |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |
| 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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais |
| Beneficiário: | Munir Salomao Skaf |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |
| Processo FAPESP: | 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo |
| Beneficiário: | Sandra Eliza Fontes de Avila |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |