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.
Publicado
30/06/2020
Como Citar

Selecione um Formato
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.