Propriedades do Problema da Floresta Geradora k-Rotulada
Resumo
Consideramos o problema da Floresta Geradora k-Rotulada, que consiste em encontrar uma floresta geradora de um grafo colorido em arestas com a menor quantidade de árvores e no máximo k cores. Derivamos duas caracterizações para o problema e mostramos estratégias para converter uma instância em outra equivalente. Esses resultados impactam o desenvolvimento de abordagens de solução. Identificamos também alguns casos polinomiais.
Palavras-chave:
Floresta geradora k-rotulada, árvore geradora minimamente rotulada, Grafo rotulado em arestas
Referências
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.
Publicado
30/06/2020
Como Citar
DE ABREU FIGUEREDO, Pedro Jorge; CAMPÊLO, Manoel.
Propriedades do Problema da Floresta Geradora k-Rotulada. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
