Recoloração convexa de grafos

Autor(es)

Ana Paula dos Santos Dantas

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2019-09-27

Membros da banca

Zanoni Dias; Rafael Crivellari Saliba Schouery; Simone de Lima Martins

• Orientador: Zanoni Dias; Cid Carvalho de Souza

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 (AU)

• Processo FAPESP: 18/04760-3 - Recoloração convexa de grafos
• Beneficiário: Ana Paula dos Santos Dantas
• Modalidade de apoio: Bolsas no Brasil - Mestrado