Defesa de Mestrado de Ana Paula dos Santos Dantas

Título do Trabalho
Recoloração Convexa de Grafos
Candidato(a)
Ana Paula dos Santos Dantas
Nível
Mestrado
Data
Add to Calender 2019-09-27 00:00:00 2019-09-27 00:00:00 Defesa de Mestrado de Ana Paula dos Santos Dantas Recoloração Convexa de Grafos Sala 85 do IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
13:30
Local
Sala 85 do IC 2
Orientador(a)
Zanoni Dias
Banca Examinadora

* Titulares

Unidade/Instituição

Zanoni Dias

IC/UNICAMP

Simone de Lima Martins

IC/UFF

Rafael Crivellari Saliba Schouery

IC/UNICAMP

 

* Suplentes

Unidade/Instituição

Guilherme Pimentel Telles

IC/UNICAMP

Yuri Abitbol De Menezes Frota

IC/UFF

Resumo

Neste trabalho, investigamos o problema de recoloração convexa em árvores e em grafos gerais. Consideramos uma coloração como uma função que define uma cor para um vértice independente de sua vizinhança. Desse modo, uma coloração é dita convexa se os conjuntos formados por todos os vértices de mesma cor induzem 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, de modo que a coloração se torne convexa. Esse problema é mais comumente estudado em árvores devido a sua origem no estudo de árvores filogenéticas. Tratamos de uma versão do problema em árvores em que a coloração é aplicada apenas nas folhas. Para essa versão do problema, fizemos experimentos com a modelagem de Chopra et al. para o problema em árvores, e verificamos que o mesmo 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) para o problema e usamos o modelo de programação linear inteira de Campêlo et al. para verificar a qualidade das soluções. Nesses experimentos, nossa heurística recoloriu um número similar ao do modelo. Além disso, adaptamos a heurística para uma versão do problema de recoloração que restringe quais vértices podem ser recoloridos e quais podem apenas ter suas cores removidas. Essa versão é conhecida como Problema de Recoloração Convexa Restrito. Criamos benchmarks de instâncias para todas as versões do problema e, sempre que necessário, usamos testes estatísticos para fundamentar nossas escolhas.