Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/335625
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Recoloração convexa de grafos
Title Alternative: Convex graph recoloring
Author: Dantas, Ana Paula dos Santos, 1996-
Advisor: Dias, Zanoni, 1975-
Abstract: Resumo: Consideramos uma coloração de um grafo como uma função que define uma cor para todo vértice, independente de sua vizinhança. Desse modo, uma coloração é dita convexa se o conjunto formado por todos os vértices de mesma cor induz um subgrafo conexo. Dada uma coloração qualquer, o Problema de Recoloração Convexa busca pelo menor número de vértices que precisam mudar de cor, isto é, ser recoloridos, de modo que a coloração se torne convexa. Esse problema é mais comumente abordado na sua versão em árvo- res devido à sua origem no estudo de árvores filogenéticas. Neste trabalho tratamos de uma variante do problema em árvores cuja coloração é aplicada apenas nas folhas. Para essa versão do problema, fizemos experimentos com o modelo de Programação Linear Inteira (pli) proposto para o problema em árvores por Chopra et al. [9]. Verificamos que o modelo também tem bons resultados para a versão do problema em árvores com apenas as folhas coloridas. Para a versão do problema em grafos gerais, propomos uma heurística baseada no grasp (Greedy Randomized Adaptive Search Procedure). Execu- tamos extensivos experimentos com essa heurística e usamos o modelo de Programação Linear Inteira proposto por Campêlo et al. [7] para verificar a qualidade das soluções do grasp. A heurística grasp recoloriu um número de vértices menor que o modelo em uma quantidade significativa de instâncias, quando ambos dispõem da mesma quantidade de recursos computacionais. Além disso, adaptamos a heurística e o modelo pli para uma versão do problema de recoloração conhecida como Problema de Recoloração Con- vexa Restrita. Nessa versão, restringimos quais vértices podem ser recoloridos e quais podem apenas ter suas cores removidas. Criamos benchmarks de instâncias para todas as versões estudadas do problema e, sempre que necessário, usamos testes estatísticos para fundamentar as escolhas das melhores versões da heurística

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
Subject: Recoloração convexa
Otimização combinatória
GRASP (Meta-heurística)
Programação linear inteira
Language: Português
Editor: [s.n.]
Citation: DANTAS, Ana Paula dos Santos. Recoloração convexa de grafos. 2019. 1 recurso online (75 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2019
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Dantas_AnaPaulaDosSantos_M.pdf1.23 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.