Convex graph Recoloring

• Grant number: 18/04760-3
• Support Opportunities: 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
• Acordo de Cooperação: Coordination of Improvement of Higher Education Personnel (CAPES)
• Principal Investigator: Zanoni Dias
• Grantee: Ana Paula dos Santos Dantas
• Host 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)

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. (17/16246-0, 17/12646-3, 15/11937-9, 18/04760-3)

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. (15/11937-9, 17/12646-3, 18/04760-3, 17/16246-0)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

DANTAS, Ana Paula dos Santos. Convex graph recoloring. 2019. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.