Defesa de Qualificação de Dissertação: José Robertty de Freitas Costa

Título: O Problema da k-Floresta Geradora Mínima

Data: 26/08/2022

Horário: 09h30

Local: Videoconferência

 

Resumo:

O problema da k-Floresta Geradora Mínima (k-FGM) consiste em, dados um grafo G não direcionado com pesos/custos nas arestas e um inteiro k, encontrar uma floresta geradora de G com k árvores, de forma a minimizar o peso da árvore mais pesada. Neste trabalho apresentamos duas heurísticas, duas formulações de programação inteira e um algoritmo enumerativo para o problema k-FGM. Além disso, provamos um limite inferior para o problema e propomos desigualdades válidas para os modelos apresentados. Por fim, apresentamos resultados computacionais preliminares.

Banca examinadora:

  • Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
  • Prof. Dr. Rafael Castro de Andrade (UFC)
  • Prof. Dr. Fábio Carlos Sousa Dias (UFC)

Última atualização (Qua, 17 de Agosto de 2022 22:23)