Uma estratégia para selecionar vértices como candidatos a roteadores em uma árvore de Steiner
Resumo
O problema da árvore de Steiner em grafos é NP-difícil, no entanto, algoritmos que fazem uso de heurísticas conseguem obter resultados próximos da solução ótima em tempo polinomial. Neste trabalho apresentamos um novo algoritmo baseado em um algoritmo exato enumerativo da literatura. A heurística proposta seleciona vértices como candidatos a serem roteadores na árvore de Steiner.
Referências
Byrka, J., Grandoni, F., Rothvoss, T., and Sanità, L. (2013). Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1–6:33.
Dourado, M., Oliveira, R., and Protti, F. (2014). Algorithmic aspects of steiner convexity and enumeration of steiner trees. Annals of Operations Research, 223(1):155–171.
Dreyfus, S. E. and Wagner, R. A. (1971). The steiner problem in graphs. Networks, 1(3):195–207.
Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA.
Kou, L., Markowsky, G., and Berman, L. (1981). A fast algorithm for steiner trees. Acta Informatica, 15(2):141–145.
Pajor, T., Uchoa, E., and Werneck, R. F. (2014). A robust and scalable algorithm for the steiner problem in graphs. CoRR, abs/1412.2787.
Robins, G. and Zelikovsky, A. (2000). Improved steiner tree approximation in graphs. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, pages 770–779, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.
Takahashi, H. and Matsuyama, A. (1980). An approximate solution for the steiner problem in graphs. In Math. Jap, pages 24:573–577.
Vygen, J. (2011). Faster algorithm for optimum steiner trees. Information Processing Letters, 111(21):1075 – 1079.
Wu, Y. F., Widmayer, P., and Wong, C. K. (1986). A faster approximation algorithm for the steiner problem in graphs. Acta Inf., 23(2):223–229.
Zelikovsky, A. Z. (1993). An 11/6-approximation algorithm for the network steiner problem. Algorithmica, 9(5):463–470.
Dourado, M., Oliveira, R., and Protti, F. (2014). Algorithmic aspects of steiner convexity and enumeration of steiner trees. Annals of Operations Research, 223(1):155–171.
Dreyfus, S. E. and Wagner, R. A. (1971). The steiner problem in graphs. Networks, 1(3):195–207.
Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA.
Kou, L., Markowsky, G., and Berman, L. (1981). A fast algorithm for steiner trees. Acta Informatica, 15(2):141–145.
Pajor, T., Uchoa, E., and Werneck, R. F. (2014). A robust and scalable algorithm for the steiner problem in graphs. CoRR, abs/1412.2787.
Robins, G. and Zelikovsky, A. (2000). Improved steiner tree approximation in graphs. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, pages 770–779, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.
Takahashi, H. and Matsuyama, A. (1980). An approximate solution for the steiner problem in graphs. In Math. Jap, pages 24:573–577.
Vygen, J. (2011). Faster algorithm for optimum steiner trees. Information Processing Letters, 111(21):1075 – 1079.
Wu, Y. F., Widmayer, P., and Wong, C. K. (1986). A faster approximation algorithm for the steiner problem in graphs. Acta Inf., 23(2):223–229.
Zelikovsky, A. Z. (1993). An 11/6-approximation algorithm for the network steiner problem. Algorithmica, 9(5):463–470.
Publicado
26/07/2018
Como Citar
MARTINEZ, João Guilherme; DE FREITAS, Rosiane; DA SILVA, Altigran; PROTTI, Fábio.
Uma estratégia para selecionar vértices como candidatos a roteadores em uma árvore de Steiner. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 137-140.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3171.
