| Grant number: | 18/04760-3 |
| Support Opportunities: | Scholarships in Brazil - Master |
| Start date: | August 01, 2018 |
| End date: | September 30, 2019 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
| Agreement: | 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) | |
| News published in Agência FAPESP Newsletter about the scholarship: | |
| More itemsLess items | |
| TITULO | |
| Articles published in other media outlets ( ): | |
| More itemsLess items | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |