Título: Problema da Floresta Geradora k-Rotulada

Data: 23/08/2019

Horário: 10:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Neste trabalho, estudamos o problema da Floresta Geradora k-Rotulada. Dentre os problema em grafos coloridos em arestas, neste temos como objetivo encontrar um subgrafo gerador que é uma floresta com a menor quantidade de componentes e com um fator limitante inteiro positivo k para o número de rótulos distintos usados. O problema é NP-Completo, por ser generalização do problema da Árvore Geradora Minimamente Rotulada, e a maioria dos métodos propostos pela literatura são metaheurísticas. Estudamos características do problema e relacionamos com a literatura pertinente em grafos coloridos para propor três modelos matemáticos de programação inteira mista binária e inteira binária. Propomos métodos Branch & Cut para resolver o problema de forma exata, usando algoritmo para separação de Cortes Coloridos. Além disso, propomos uma paralelização para único método exato disponível na literatura, que aplica um procedimento backtracking. Apresentamos experimentos computacionais preliminares com os modelos e o método backtracking, usando instâncias de teste sugeridas na literatura.  Por fim, propomos algumas melhorias para os métodos de resolução.

Banca:

• Prof. Dr. Manoel Campelo (MDCC/UFC - Orientador)
• Prof. Dr. Rafael Andrade (MDCC/UFC)
• Prof. Dr. Lucídio Cabral (UFPB)