Properties of the k-labeled spanning forest problem
Abstract
We consider the k-Labeled Spanning Forest problem, which consists in finding a spanning forest of an edge-labeled graph with the least number of trees and at most k colors. We derive two characterizations of the problem and show strategies to convert an instance into an equivalent one. These results impact the development of solution approaches. We also identify some polynomial cases.
Keywords:
k-labeled spanning forest, Minimum labeling spanning tree, Edge labeled graph
References
Cerulli, R., Fink, A., Gentili, M., and Raiconi, A. (2014). The k-labeled spanning forest problem. Procedia - Social and Behavioral Sciences, 108:153–163.
Chang, R.-S. and Shing-Jiuan, L. (1997). The minimum labeling spanning trees. Information Processing Letters, 63(5):277–282.
Consoli, S. and Pérez, J. A. M. (2015). Variable neighbourhood search for the k-labelled spanning forest problem. Electronic Notes in Discrete Mathematics, 47:29–36.
Consoli, S., Pérez, J. A. M., and Mladenovic, N. (2017). Comparison of metaheuristics for the k-labeled spanning forest problem. International Transactions in Operational Research, 24(3):559–582.
Figueredo, P. J. (2020). O problema da floresta geradora k-rotulada. Master’s thesis, Universidade Federal do Ceará, Brasil.
Miller, C. E., Tucker, A. W., and Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. J. ACM, 7(4):326–329.
Padberg, M. W. and Wolsey, L. A. (1983). Trees and cuts. In Berge, C., Bresson, D., Ca- mion, P., Maurras, J., and Sterboul, F., editors, Combinatorial Mathematics, volume 75 of North-Holland Mathematics Studies, pages 511 – 517.
Silva, T. G. d. (2018). The Minimum Labeling Spanning Tree and Related Problems. PhD thesis, Universidade Federal Fluminense (Brazil), Université d’Avignon et des Pays de Vaucluse (France).
Wan, Y., Chen, G., and Xu, Y. (2002). A note on the minimum label spanning tree. Information Processing Letters, 84(2):99 – 101.
Chang, R.-S. and Shing-Jiuan, L. (1997). The minimum labeling spanning trees. Information Processing Letters, 63(5):277–282.
Consoli, S. and Pérez, J. A. M. (2015). Variable neighbourhood search for the k-labelled spanning forest problem. Electronic Notes in Discrete Mathematics, 47:29–36.
Consoli, S., Pérez, J. A. M., and Mladenovic, N. (2017). Comparison of metaheuristics for the k-labeled spanning forest problem. International Transactions in Operational Research, 24(3):559–582.
Figueredo, P. J. (2020). O problema da floresta geradora k-rotulada. Master’s thesis, Universidade Federal do Ceará, Brasil.
Miller, C. E., Tucker, A. W., and Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. J. ACM, 7(4):326–329.
Padberg, M. W. and Wolsey, L. A. (1983). Trees and cuts. In Berge, C., Bresson, D., Ca- mion, P., Maurras, J., and Sterboul, F., editors, Combinatorial Mathematics, volume 75 of North-Holland Mathematics Studies, pages 511 – 517.
Silva, T. G. d. (2018). The Minimum Labeling Spanning Tree and Related Problems. PhD thesis, Universidade Federal Fluminense (Brazil), Université d’Avignon et des Pays de Vaucluse (France).
Wan, Y., Chen, G., and Xu, Y. (2002). A note on the minimum label spanning tree. Information Processing Letters, 84(2):99 – 101.
Published
2020-06-30
How to Cite
DE ABREU FIGUEREDO, Pedro Jorge; CAMPÊLO, Manoel.
Properties of the k-labeled spanning forest problem. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 69-72.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11092.
