Full text
| |
| Author(s): |
Ana Paula dos Santos Dantas
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2019-09-27 |
| Examining board members: |
Zanoni Dias;
Rafael Crivellari Saliba Schouery;
Simone de Lima Martins
|
| Advisor: | Zanoni Dias; Cid Carvalho de Souza |
| Abstract | |
We consider a coloring of a graph to be a function that assigns a color to a vertex, regardless of its neighborhood. In this sense, a coloring is said to be convex if every set formed by all of the vertices with the same color induces a connected subgraph. The Convex Recoloring Problem asks to find the minimum number of vertex recolorings needed to turn a coloring convex. This problem is most commonly treated in its version that considers trees due to its origins in the study of phylogenetic trees. We worked on a version of the problem in which the initial coloring is applied only on the leaves of the tree. For this version, we experimented with the mathematical model proposed for the problem on trees by Chopra et al. [9]. With these experiments, we found that the model also has good results for the version with the coloring only on the leaves. For the version of the problem on general graphs, we proposed a heuristic based on the Greedy Randomized Adaptive Search Procedure (grasp) and used a mathematical model proposed by Campêlo et al. [7] to verify the quality of the solutions given by the grasp heuristic. In these experiments, our heuristic recolored less vertices than the model in a significant number of instances, when given the same computational resources. We also propose adaptations for the grasp to solve a version of the recoloring problem known as Minimum Restricted Recoloring Problem. In this version, we restrict which vertices can be recolored and which vertices can only have their color removed. We created sets of benchmark instances for all the versions of the problem, and performed statistical analysis to support our conclusions, when necessary (AU) | |
| FAPESP's process: | 18/04760-3 - Convex graph Recoloring |
| Grantee: | Ana Paula dos Santos Dantas |
| Support Opportunities: | Scholarships in Brazil - Master |