Resultados de NP-dificuldade e Aproximação para o Problema da k−Floresta Geradora Minimamente Rotulada
Resumo
Dado um grafo colorido em arestas G, o problema da k-floresta geradora minimamente rotulada consiste em encontrar uma floresta geradora F de G com número mínimo de cores e número de componentes limitado por k. Neste trabalho, apresentamos uma prova da NP-completude do problema em grafos split e propomos um algoritmo aproximativo para solucioná-lo.Referências
Cerulli, R., Ambrosio, C., Serra, D., and Sorgente, C. (2024). The budgeted labeled minimum spanning tree problem. Mathematics, 12(2).
Cerulli, R., Fink, A., and Gentili, M. (2006). Extensions of the minimum labelling spanning tree problem. Journal of Telecommunications and Information Technology, 26(4):39–45.
Chang, R.-S. and Leu, S.-J. (1997). The minimum labeling spanning trees. Inf. Process. Lett., 63(5):277–282.
Chwatal, A. M., Raidl, G. R., and Dietzel, O. (2007). Compressing fingerprint templates by solving an extended minimum label spanning tree problem.
Corrêa, L. and Campêlo, M. (2024). O problema da k-floresta geradora minimamente rotulada. In Anais do LVI SBPO, Fortaleza.
Fellows, M. R., Guo, J., and Kanj, I. (2010). The parameterized complexity of some minimum label problems. Journal of Computer and System Sciences, 76(8):727–740.
Krumke, S. O. and Wirth, H.-C. (1998). On the minimum label spanning tree problem. Information Processing Letters, 66(2):81–85.
West, D. (1996). Introduction to Graph Theory. Introduction to Graph Theory. Prentice Hall.
Xiong, Y., Golden, B., and Wasil, E. (2005). Worst-case behavior of the mvca heuristic for the minimum labeling spanning tree problem. Operations Research Letters, 33(1):77–80.
Cerulli, R., Fink, A., and Gentili, M. (2006). Extensions of the minimum labelling spanning tree problem. Journal of Telecommunications and Information Technology, 26(4):39–45.
Chang, R.-S. and Leu, S.-J. (1997). The minimum labeling spanning trees. Inf. Process. Lett., 63(5):277–282.
Chwatal, A. M., Raidl, G. R., and Dietzel, O. (2007). Compressing fingerprint templates by solving an extended minimum label spanning tree problem.
Corrêa, L. and Campêlo, M. (2024). O problema da k-floresta geradora minimamente rotulada. In Anais do LVI SBPO, Fortaleza.
Fellows, M. R., Guo, J., and Kanj, I. (2010). The parameterized complexity of some minimum label problems. Journal of Computer and System Sciences, 76(8):727–740.
Krumke, S. O. and Wirth, H.-C. (1998). On the minimum label spanning tree problem. Information Processing Letters, 66(2):81–85.
West, D. (1996). Introduction to Graph Theory. Introduction to Graph Theory. Prentice Hall.
Xiong, Y., Golden, B., and Wasil, E. (2005). Worst-case behavior of the mvca heuristic for the minimum labeling spanning tree problem. Operations Research Letters, 33(1):77–80.
Publicado
20/07/2025
Como Citar
CORRÊA, Kennedy; CAMPÊLO, Manoel.
Resultados de NP-dificuldade e Aproximação para o Problema da k−Floresta Geradora Minimamente Rotulada. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 65-69.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.8860.
