Formulations for the Minimum Spanning k-Forest Problem
Abstract
We introduce two integer programming formulations for the Minimum Spanning k-Forest problem. We evaluate their computational performance with test instances. We compare the number of obtained optimal solutions and computing time as a function of parameter k.
Keywords:
Minimum Spanning k-Forest. Integer Programming. Combinatorial Optimization
References
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.
Published
2022-07-31
How to Cite
COSTA, José Robertty de Freitas; SOUSA, Gabriel Hellen de; CAMPÊLO, Manoel.
Formulations for the Minimum Spanning k-Forest Problem. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
