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:
Última atualização (Qua, 17 de Agosto de 2022 22:23)