Formulações para o Problema da k-Floresta Geradora Mínima

  • José Robertty de Freitas Costa UFC
  • Gabriel Hellen de Sousa UFC
  • Manoel Campêlo UFC

Resumo


Introduzimos duas formulações de programação inteira para o problema da k-Floresta Geradora Mínima. Avaliamos seu desempenho computacional com instâncias de teste. Comparamos a quantidade de soluções ótimas encontradas e o tempo médio demandado em função do parâmetro k.

Palavras-chave: K-Floresta Geradora Mínima, Programação Inteira, Otimização Combinatória

Referências

Campêlo, M., Campos, V., and Corrêa, R. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156(7):1097–1111.

Desrochers, M. and Laporte, G. (1991). Improvements and extensions to the Miller Tucker-Zemlin subtour elimination constraints. Operations Res. Letters, 10:27 – 36.

Madkour, A.-R., Nadolny, P., and Wright, M. (2019). Finding minimum spanning forests in a graph. In Proc. of The Midwest Instruction and Computing Symposium (MICS).

Vaishali, S., Atulya, M., and Purohit, N. (2018). Efficient algorithms for a graph partitioning problem. In International Workshop on Frontiers in Algorithmics, pages 29–42.
Publicado
31/07/2022
COSTA, José Robertty de Freitas; SOUSA, Gabriel Hellen de; CAMPÊLO, Manoel. Formulações para o Problema da k-Floresta Geradora Mínima. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 101-104. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.223148.