Formulações para o Problema da k-Floresta Geradora Mínima
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.
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
Como Citar
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.
