Advanced search
Start date
Betweenand

Convex graph Recoloring

Grant number: 18/04760-3
Support type:Scholarships in Brazil - Master
Effective date (Start): August 01, 2018
Effective date (End): September 30, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Cooperation agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
Principal researcher:Zanoni Dias
Grantee:Ana Paula dos Santos Dantas
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Given a graph G, a set of colors C and a coloring function C that assigns a color of C to the vertices of G, we define a coloring as convex if every color class induces a connected subgraph of G. When a given coloring is not convex, we may change the color of some vertices in order to obtain a convex coloring. A Minimum Convex Recoloring finds the smallest number possible of color changes necessary to transform a coloring into a convex coloring. This problem comes from the study of phylogenetic trees, in which convexity indicates that there were no convergences or reversions during the evolution of a species. Besides biology applications, the problem applies to computer networks with minor changes. In this project, we study the problem applied to trees and general graphs. We will develop algorithms with the meta-heuristics GRASP and mathematical models for the problem versions studied. Lastly, we will create experiments comparing the performance of our algorithms and those presents in current literature. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
DANTAS, ANA PAULA S.; DE SOUZA, CID C.; DIAS, ZANONI. A heuristic for the convex recoloring problem in graphs. International Transactions in Operational Research, v. 29, n. 3, p. 1454-1478, MAY 2022. Web of Science Citations: 0.
DANTAS, ANA PAULA S.; DE SOUZA, CID C.; DIAS, ZANONI. A heuristic for the convex recoloring problem in graphs. International Transactions in Operational Research, NOV 2020. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.