Novo teste de redução para o problema da árvore de Steiner com coleta de prêmios

• Gabriel M. de Azevedo USP https://orcid.org/0000-0003-2715-7115
• Carlos E. Ferreira USP http://orcid.org/0000-0003-4804-5788

DOI: https://doi.org/10.5753/etc.2021.16379

Resumo

O problema da árvore de Steiner com coleta de prêmios consiste na busca de um subgrafo que minimiza a soma dos valores das arestas contidas no subgrafo e dos vértices não contidos. Apresentamos um novo teste de redução para o problema e resultados computacionais com instâncias da literatura.

Palavras-chave: Otimização Combinatória, Algoritmos, Árvore de Steiner

Referências

DIMACS (2014). 11th dimacs implementation challenge. dimacs11.zib.de. Acessado em 21/06/2020.

Karp, R. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85–103.

Ljubić, I., Weiskircher, R., Pferschy, U., Klau, G., Mutzel, P., and Fischetti, M. (2005). An algorithmic framework for the exact solution of the prize-collecting steiner tree problem. Mathematical Programming, 105(2-3):427–449.

Rehfeldt, D. and Koch, T. (2020). On the exact solution of prize-collecting steiner tree problems. Technical report, Zuse Institute Berlin.

Uchoa, E. (2006). Reduction tests for the prize-collecting steiner problem. Operations Research Letters, 34(4):437–444.