Problema da árvore de Steiner: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 19h45min de 19 de outubro de 2023

Na Combinatória, o problema da árvore de Steiner, problema da autoestrada, ou problema da árvore mínima de Steiner, denominado em referência a Jakob Steiner, é um termo genérico para uma classe de problemas na otimização combinatória. Uma variante bastante conhecida, que é geralmente utilizada como sinônimo do termo problema da árvore de Steiner, é o problema da árvore de Steiner em grafos. Dado um grafo simples com os pesos das arestas não negativas e um subconjunto de vértices, geralmente referidos como terminais, o problema da árvore de Steiner em grafos requer uma árvore com menor peso que contenha todos os terminais (mas poderá incluir vértices adicionais) e minimiza o total dos pesos de suas arestas. Outras variantes bastante conhecidas são o problema da árvore de Steiner Euclidiana e o problema da árvore de Steiner retilinear.

O problema da árvore de Steiner em grafos pode ser visto como uma generalização de dois outros problemas: o problema do caminho mínimo (não negativo) e o problema da árvore de extensão mínima. Se um problema da árvore de Steiner em grafos contém exatamente dois terminais, a procura se restringe ao caminho mínimo. Se, por outro lado, todos os vértices são terminais, o problema da árvore de Steiner em grafos é equivalente à árvore de extensão mínima. No entanto, por mais que o problema do caminho mínimo não negativo e da árvore de extensão mínima são resolvidos em tempo polinomial, nenhuma solução do tipo é conhecida para o problema da árvore de Steiner em grafos. Sua variante de decisão, em que se pergunta se uma determinada entrada tem uma árvore de peso menor que um determinado limite, é NP-completa, o que implica que a variante de otimização, pedindo pela árvore de peso mínimo num dado grafo, é NP-difícil. Na verdade, um deles estava entre os 21 problemas originais NP-completos de Karp. O problema da árvore de Steiner em grafos tem aplicações em layout de circuito ou em design de rede. No entanto, aplicações práticas geralmente requerem variações, o que aumenta a quantidade de variantes do problema da árvore de Steiner.

A maioria das versões do problema da árvore de Steiner são NP-difíceis, mas alguns casos restritos podem ser resolvidos em tempo polinomial. Apesar do pessimismo da complexidade de pior caso, diversas variantes do problema da árvore de Steiner, incluindo o problema da árvore de Steiner em grafos e problema da árvore de Steiner retilinear, podem ser resolvidos eficientemente na prática, mesmo para problemas do mundo real em larga escala.^[1]^[2]

Árvore de Steiner euclidiano

O problema original foi enunciado na forma em que se tornou conhecido como o problema da árvore de Steiner euclidiana ou problema geométrico da árvore de Steiner: Dados $N$ pontos em um plano, o objetivo é conectá-los por linhas de comprimento total mínimo de tal forma que quaisquer dois pontos podem ser interligados por segmentos de reta diretamente ou através de outros pontos e segmentos de reta. Pode ser mostrado que os segmentos de reta não se cruzam uns aos outros, exceto nas extremidades e formam uma árvore, daí o nome do problema.

O problema para $N$ = 3 tem sido estudado há muito tempo e rapidamente se estendeu ao problema de encontrar uma rede estelar com um único centro conectando todos os $N$ pontos dados, com o comprimento total mínimo. No entanto, embora o problema completo da árvore de Steiner tenha sido formulado em uma carta por Gauss, seu primeiro tratamento sério foi em um artigo de 1934 escrito em tcheco por Vojtěch Jarník e Miloš Kössler. Este artigo foi muito ignorado, mas já continha "virtualmente todas as propriedades gerais das árvores de Steiner" posteriormente atribuídas a outros pesquisadores, incluindo a generalização do problema do plano para dimensões maiores.^[3]

Para o problema da árvore de Steiner euclidiana, pontos adicionados ao grafo (pontos de Steiner) devem ter um grau 3, e as três arestas incidentes ao ponto devem formar 3 ângulos de 120 graus (ver ponto de Fermat). Segue que o número máximo de pontos que uma árvore de Steiner pode ter é $N$ - 2, em que $N$ é o número de pontos inicialmente dados.

Para $N$ = 3, existem dois casos possíveis: se o triângulo formado pelos pontos dados tem todos os ângulos que são menores do que 120 graus, a solução é dada por um ponto de Steiner localizado no ponto de Fermat; caso contrário, a solução é dada pelos dois lados do triângulo, que se encontram no ângulo igual ou maior que 120 graus.

Para $N$ geral, o problema da árvore euclidiana de Steiner é NP-difícil, e, portanto, não se sabe se uma solução ótima pode ser encontrada por meio de um algoritmo de tempo polinomial. No entanto, existe um esquema de aproximação de tempo polinomial (PTAS) para árvores de Steiner euclidiana, isto é, uma solução quase ótima pode ser encontrada em tempo polinomial.^[4] Não se sabe se o problema da árvore de Steiner euclidiana é NP-completo, uma vez que a sua pertinência à classe de complexidade NP não é conhecida.

Árvore de Steiner retilinear

O problema mínimo da árvore de Steiner retilinear é uma variante do problema geométrico da árvore de Steiner no plano, no qual a distância euclidiana é substituído pela distância retilínea. O problema surge na concepção física de automação de design eletrônico. Em circuitos de VLSI [en], a distribuição de fios é realizada por fios que são muitas vezes restringidos pelas regras de design para percorrer somente em direções verticais e horizontais, de modo que o problema da árvore retilínea de Steiner pode ser utilizado para modelar o roteamento de redes com mais do que dois terminais.^[5]

Árvore de Steiner em grafos e variantes

As árvores de Steiner também foram estudadas no contexto de grafos com peso. O protótipo é, sem dúvida, o problema da árvore de Steiner em grafos. Seja $G$ = ( $V$ , $E$ ) um grafo não direcionado como vértices não negativos de peso $c$ e um subconjunto $S$ ⊆ $V$ de vértices, chamados de terminais. Uma árvore de Steiner é uma árvore no grafo $G$ que abrange todos os vértices de $S$ . Existem duas versões do problema: no problema de otimização associado com árvores de Steiner, a tarefa é encontrar uma árvore de Steiner de peso mínimo; no problema de decisão, os pesos das arestas são inteiros e a tarefa é determinar se exite uma árvore de Steiner que de peso total no máximo k existe. O problema da decisão foi um dos 21 problemas NP-completos de Karp; daí o problema de otimização é NP-difícil. Os problemas da árvore de Steiner em grafos são aplicadoa a varios problemas de empresa e industria,^[6] incluindo roteamento multicast^[7] e bioinformática.^[8]

Um caso especial deste problema é quando $G$ é um grafo completo, cada vértice $v$ ∈ $V$ corresponde a um ponto em um espaço métrico, e os pesos das arestas $w$ ( $e$ ) para cada $e$ ∈ $E$ correspondem às distâncias no espaço. Em outras palavras, os pesos das arestas satisfazem a desigualdade triangular. Esta variante é conhecida como o problema da árvore de Steiner métrico. Dada uma instância (não-métrica) do problema da árvore de Steiner, podemos transformá-la em tempo polinomial em uma instância equivalente do problema métrico da árvore de Steiner; a transformação preserva o fator de aproximação.^[9]

Embora a versão euclidiana admita um PTAS, sabe-se que o problema métrico da árvore de Steiner é APX-completo, isto é, a menos que P = NP, é impossível de alcançar proporções de aproximação que são arbitrariamente próximas de 1 em tempo polinomial. Há um algoritmo de tempo polinomial que aproxima a árvore mínima de Steiner dentro de um fator de $\ln(4)+\epsilon \approx 1.386$ ;^[10] No entanto, a aproximação dentro de um fator de $96/95\approx 1.0105$ é NP-difícil.^[11] Para o caso restrito do problema da árvore de Steiner com distâncias 1 e 2, um algoritmo de aproximação com fator 1,25 é conhecido.^[12] Karpinski e Alexander Zelikovsky construiram um PTAS para as instâncias densas do problema da árvore de Steiner.^[13]

Em um caso especial do problema de grafo, o problema da árvore de Steiner para gratos quase-bipartidos, $S$ tem que incluir pelo menos uma extremidade de cada aresta de $G$ .

O problema da árvore de Steiner também tem sido investigado em dimensões mais elevadas e em várias superfícies. Algoritmos para encontrar a árvore mínima de Steiner tem sido encontrados na esfera, toro, plano projetivo, cones largos e estreitos, e outros.^[14]

Outras generalizações do problema da árvore de Steiner são o problema de k-arestas-conexo da rede de Steiner e o problema de k-vértices-conexos da rede de Steiner, no qual o objetivo é encontrar um grafo k-aresta-conexo ou um grafo k-vértice-conexo em vez do que grafo conexo qualquer. Outra generalização bastante estudada é o problema de projeto de redes sobrevivível, em que o objetivo é conectar cada par de vértices com um dado número (possivelmente 0) de caminhos de arestas ou vértices disjuntos.^[15]

O problema de Steiner também foi enunciado na definição geral dos espaços métricos e possivelmente para uma quantidade infinita de pontos.^[16]

Aproximando a árvore de Steiner

O problema geral de grafo da árvore de Steiner pode ser aproximado computando a árvore geradora mínima do subgrafo do fecho métrico do grafo induzido pelos vértices terminais, conforme publicado pela primeira vez por Kou et al. em 1981.^[17] O fecho métrico de um grafo $G$ é o grafo completo no qual cada aresta é ponderada pela distância do caminho mais curto entre os nós em $G$ . Esse algoritmo produz uma árvore cujo peso está dentro de um fator de $2-{\frac {2}{t}}$ do peso da árvore de Steiner ótima em que $t$ é o número de folhas na árvore de Steiner ótima; isso pode ser provado considerando o passeio do caixeiro-viajante na árvore de Steiner ótima. Uma solução aproximada é computável em tempo polinomial $O(|S||V|^{2})$ ao resolver primeiramente o problema dos caminhos mais curtos de todos os pares para computar o fecho métrico, e depois resolvendo o problema da árvore de extensão mínima.

Outro algoritmo popular para aproximar a árvore de Steiner em grafos foi publicado por Takahashi e Matsuyama em 1980.^[18] A solução deles constrói incrementalmente a árvore de Steiner, começando a partir de um vértice arbitrário e adicionando repetidamente o caminho mais curto da árvore para o vértice mais próximo em S que ainda não foi adicionado. Esse algoritmo também tem um tempo de execução de $O(|S||V|^{2})$ e produz uma árvore cujo peso está dentro de $2-{\frac {2}{|S|}}$ do ótimo.

Em 1986, Wu et al.^[19] melhoraram drasticamente o tempo de execução, evitando o pré-cálculo dos caminhos mais curtos entre todos os pares de vértices. Em vez disso, eles adotaram uma abordagem semelhante à do algoritmo de Kruskal para calcular uma árvore geradora mínima, começando com uma floresta de |S| árvores disjuntas e "crescendo" simultaneamente usando uma busca em largura que se assemelha ao algoritmo de Dijkstra, mas começando a partir de múltiplos vértices iniciais. Quando a busca encontra um vértice que não pertence à árvore atual, as duas árvores são mescladas em uma. Esse processo é repetido até que reste apenas uma árvore. Usando uma estrutura de heap para implementar a fila de prioridade e uma estrutura de dados união-busca para rastrear a qual árvore pertence cada vértice visitado, esse algoritmo alcança um tempo de execução de $O(|E|\log |V|)$ , embora não melhore a proporção de custo $2-{\frac {2}{t}}$ de Kou et al.

Uma série de artigos forneceu algoritmos de aproximação para o problema da árvore de Steiner mínima com proporções de aproximação que melhorou a proporção de $2-{\frac {2}{t}}$ . A sequência culminou com o algoritmo de Robins e Zelikovsky em 2000, que melhorou esta proporção para 1,55 ao melhorar iterativamente a árvore geradora terminal de custo mínimo.^[20] Mais recentemente, entretanto, Byrka et al. provou uma aproximação de $\ln(4)+\varepsilon \leq 1.39$ usando um relaxamento da programação linear e uma técnica chamada de arredondamento randomizado, iterativo.^[10]

Complexidade parametrizada da árvore de Steiner

O problema geral da árvore de Steiner em grafos é conhecido por ser tratável em parâmetro fixo, com o número de terminais como um parâmetro, pelo algoritmo de Dreyfus-Wagner.^[21]^[22] O tempo de execução do algoritmo de Dreyfus-Wagner é $3^{|S|}{\text{poly}}(n)$ , em que $n$ é o número de vértices do grafo e $S$ o conjunto de terminais. Algoritmos mais rápidos existem, executando em tempo $c^{|S|}{\text{poly}}(n)$ para qualquer $c>2$ ou, no caso de pesos baixos, tempo $2^{|S|}{\text{poly}}(n)W$ , em que $W$ é o peso máximo de qualquer aresta.^[23]^[24] Uma desvantagem dos algoritmos mencionados anteriormente é que eles usam espaço exponencial [en]; existem algoritmos em espaço polinomial, que executa em tempo $2^{|S|}{\text{poly}}(n)W$ e tempo $(7.97)^{|S|}{\text{poly}}(n)\log W$ .^[25]^[26]

Sabe-se que o problema geral da árvore de Steiner em grafos não tem um algoritmo parametrizado que execute em tempo $2^{\epsilon t}{\text{poly}}(n)$ para qualquer $\epsilon <1$ , em que $t$ é o número de arestas da árvore de Steiner ótima, exceto se o problema de cobertura de conjuntos tenha um algoritmo que execute em tempo $2^{\epsilon n}{\text{poly}}(m)$ para algum $\epsilon <1$ , em que $n$ é o número de elementos e $m$ o número de conjuntos da instância do problema de cobertura de conjuntos.^[27] Além disso, sabe-se que o problema não admite um núcleo polinomial, exceto se ${\text{coNP}}\subseteq {\text{NP/poly}}$ , mesmo parametrizado pelo número de arestas de uma árvore de Steiner ótima e o peso de todas as arestas seja 1.^[28]

Proporção de Steiner

A proporção de Steiner é o supremo da razão entre o tamanho total da árvore geradora mínima para a árvore mínima de Steiner de um conjunto de pontos no plano euclidiano.^[29]

No problema da árvore euclidiana de Steiner, a proporção de Steiner é conjecturada a ser ${\frac {2}{\sqrt {3}}}$ . Apesar das alegações anteriores de uma prova,^[30] a conjectura ainda está em aberto.^[31] O limite superior mais amplamente aceito para o problema é 1,2134, por Chung e Graham em 1985.^[32]

No problema da árvore de Steiner retilinear, a proporção de Steiner é exatamente ${\frac {3}{2}}$ .^[33], a proporção que é a obtida por quatro pontos em um quadrado com uma árvore que utiliza 3 lados do quadrado e uma arvore de Steiner que conecta pelo centro do quadrado.^[33] Mais precisamente, para a distância $L_{1}$ o quadrado deveria ser rotacionado $45^{\circ }$ a respeito dos eixos de coordenada, enquanto que para a distância $L_{\infty }$ o quadrado deveria ser alinhado com o eixo.

Outros arquivos

Árvores de Steiner

Veja também

Problema do caixeiro-viajante

Referências

↑ Rehfeldt & Koch (2023).
↑ Juhl et al. (2018).
↑ Korte, Bernhard; Nešetřil, Jaroslav (2001). «Vojtěch Jarnik's work in combinatorial optimization». Discrete Mathematics. 235 (1–3): 1–17. MR 1829832. doi:10.1016/S0012-365X(00)00256-9. hdl:10338.dmlcz/500662
↑ Crescenzi et al. (2000).
↑ Sherwani (1993), p. 228.
↑ Ljubić, Ivana (2021). «Solving Steiner trees: Recent advances, challenges, and perspectives». Networks (em inglês). 77 (2): 177–204. ISSN 1097-0037. doi:10.1002/net.22005
↑ Novak, Roman; Rugelj, Joz̆e; Kandus, Gorazd (1 de outubro de 2001). «A note on distributed multicast routing in point-to-point networks». Computers & Operations Research (em inglês). 28 (12): 1149–1164. ISSN 0305-0548. doi:10.1016/S0305-0548(00)00029-0
↑ Klimm, Florian; Toledo, Enrique M.; Monfeuga, Thomas; Zhang, Fang; Deane, Charlotte M.; Reinert, Gesine (2 de novembro de 2020). «Functional module detection through integration of single-cell RNA sequencing data with protein–protein interaction networks». BMC Genomics. 21 (1). 756 páginas. ISSN 1471-2164. PMC 7607865. PMID 33138772. doi:10.1186/s12864-020-07144-2
↑ Vazirani (2003), pp. 27–28.
↑ ^a ^b Byrka et al. (2010).
↑ Chlebík & Chlebíková (2008).
↑ Berman, Karpinski & Zelikovsky (2009).
↑ Karpinski & Zelikovsky (1998).
↑ Smith & Winter (1995), p. 361.
↑ Kerivin, Hervé; Mahjoub, A. Ridha (2005). «Design of Survivable Networks: A survey». Networks (em inglês). 46 (1): 1–21. ISSN 0028-3045. doi:10.1002/net.20072
↑ Paolini & Stepanov (2012).
↑ Kou, Markowsky & Berman (1981).
↑ Takahashi & Matsuyama (1980).
↑ Wu, Widmayer & Wong (1986).
↑ Robins & Zelikovsky (2000).
↑ Dreyfus & Wagner (1971).
↑ Levin (1971).
↑ Fuchs et al. (2007).
↑ Björklund et al. (2007).
↑ Lokshtanov & Nederlof (2010).
↑ Fomin et al. (2015).
↑ Cygan et al. (2016).
↑ Dom, Lokshtanov & Saurabh (2014).
↑ Ganley (2004).
↑ The New York Times, 30 de outubro de 1990, reportou que uma prova foi encontrada, e que Ronald Graham, quem ofereceu 500 dólares pela prova, estava prestes a enviar um cheque aos autores.
↑ Ivanov & Tuzhilin (2012).
↑ Chung & Graham (1985).
↑ ^a ^b Hwang (1976).

Bibliografia

Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander (2009). «1.25-approximation algorithm for Steiner tree problem with distances 1 and 2». Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21–23, 2009, Proceedings. Lecture Notes in Computer Science. 5664. pp. 86–97. arXiv:0810.1851. doi:10.1007/978-3-642-03367-4_8
Bern, Marshall W.; Graham, Ronald L. (1989). «The shortest-network problem». Scientific American. 260 (1): 84–89. Bibcode:1989SciAm.260a..84B. doi:10.1038/scientificamerican0189-84
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2007). «Fourier Meets Möbius: Fast Subset Convolution». Anais do 39º Simpósio ACM sobre Teoria da Computação. pp. 67–74. arXiv:cs/0611101. doi:10.1145/1250790.1250801
Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanita, L. (2010). «An improved LP-based approximation for Steiner tree». Anais do 42º Simpósio ACM sobre Teoria da Computação. pp. 583–592. CiteSeerX 10.1.1.177.3565. doi:10.1145/1806689.1806769
Chlebík, Miroslav; Chlebíková, Janka (2008). «The Steiner tree problem on graphs: Inapproximability results». Theoretical Computer Science. 406 (3): 207–214. doi:10.1016/j.tcs.2008.06.046
Chung, F. R. K.; Graham, R. L. (1985). «A new bound for Euclidean Steiner minimal trees». Discrete geometry and convexity (New York, 1982). Annals of the New York Academy of Science. 440. New York: New York Academy of Science. pp. 328–346. Bibcode:1985NYASA.440..328C. MR 809217. doi:10.1111/j.1749-6632.1985.tb14564.x
Cieslik, Dietmar (1998). Steiner Minimal Trees. [S.l.]: Springer. 319 páginas. ISBN 0-7923-4983-0
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000). «Minimum geometric Steiner tree». A Compendium of NP Optimization Problems
Cygan, Marek; Dell, Holger; Lokshtanov, Daniel; Marx, Dániel; Nederlof, Jesper; Okamoto, Yoshio; Paturi, Ramamohan; Saurabh, Saket; Wahlström, Magnus (2016). «On Problems as Hard as CNF-SAT». ACM Transactions on Algorithms. 12 (3): 41:1–41:24. doi:10.1145/2925416
Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket (2014). «Kernelization Lower Bounds Through Colors and IDs». ACM Transactions on Algorithms. 11 (2): 13:1–13:20. doi:10.1145/2650261
Dreyfus, S.E.; Wagner, R.A. (1971). «The Steiner problem in graphs». Networks. 1 (3): 195–207. doi:10.1002/net.3230010302
Fomin, Fedor V.; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (2015). «Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree». Automata, Languages, and Programming – 42nd International Colloquium, ICALP 2015, Proceedings, Part I. pp. 494–505. doi:10.1007/978-3-662-47672-7_40
Fuchs, Benjamin; Kern, Walter; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter; Wang, Xinhui (2007). «Dynamic Programming for Minimum Steiner Trees» (PDF). Theory of Computing Systems. 41 (3): 493–500. doi:10.1007/s00224-007-1324-4
Ganley, Joseph L. (2004). «Steiner ratio». In: Black, Paul E. Dictionary of Algorithms and Data Structures. [S.l.]: U.S. National Institute of Standards and Technology. Consultado em 24 de maio de 2012
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1045-5, W. H. Freeman, pp. 208–209
Hwang, F. K. (1976). «On Steiner minimal trees with rectilinear distance». SIAM Journal on Applied Mathematics. 30 (1): 104–114. doi:10.1137/0130013
Hwang, F. K.; Richards, D. S.; Winter, P. (1992). The Steiner Tree Problem. Col: Annals of Discrete Mathematics. 53. North-Holland: Elsevier. ISBN 0-444-89098-X
Ivanov, Alexander; Tuzhilin, Alexey (1994). Minimal Networks: The Steiner Problem and Its Generalizations. N.W., Boca Raton, Florida: CRC Press. ISBN 978-0-8493-8642-8. (pede registo (ajuda))
Ivanov, Alexander; Tuzhilin, Alexey (2000). Branching solutions to one-dimensional variational problems. Singapore-New Jersey-London-Hong Kong: World Scientific. ISBN 978-981-02-4060-8
Ivanov, Alexander; Tuzhilin, Alexey (2003). Extreme Networks Theory (em Russian). Moscow-Izhevsk: Institute of Computer Investigations. ISBN 5-93972-292-X
Ivanov, Alexander; Tuzhilin, Alexey (2012). «The Steiner ratio Gilbert–Pollak conjecture is still open: Clarification statement». Algorithmica. 62 (1–2): 630–632. doi:10.1007/s00453-011-9508-3
Ivanov, Alexander; Tuzhilin, Alexey (2015). «Branched coverings and Steiner ratio». International Transactions in Operational Research. 23 (5): 875–882. arXiv:1412.5433. doi:10.1111/itor.12182
Juhl, D.; Warme, D.M.; Winter, P.; Zachariasen, M. (janeiro de 2018). «The GeoSteiner Software Package for computing Steiner trees in the plane: an updated computational study». Mathematical Programming Computation. 10 (4): 487–532. doi:10.1007/s12532-018-0135-8
Rehfeldt, D.; Koch, T. (fevereiro de 2023). «Implications, conflicts, and reductions for Steiner trees». Mathematical Programming. 197 (2): 903–966. doi:10.1007/s10107-021-01757-5
Karpinski, Marek; Zelikovsky, Alexander (1998). «Approximating dense cases of covering problems». Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 40. American Mathematical Society. pp. 169–178
Korte, Bernhard; Vygen, Jens (2006). «Section 20.1». Combinatorial Optimization: Theory and Algorithms 3rd ed. [S.l.]: Springer. ISBN 3-540-25684-9
Kou, L.; Markowsky, G.; Berman, L. (1 de junho de 1981). «A fast algorithm for Steiner trees». Acta Informatica. 15 (2): 141–145. doi:10.1007/BF00288961
Levin, A. Yu. (1971). «Algorithm for the shortest connection of a group of graph vertices». Soviet Mathematics Doklady. 12: 1477–1481
Lokshtanov, Daniel; Nederlof, Jesper (2010). «Saving space by algebraization». Anais do 42º Simpósio ACM sobre Teoria da Computação. pp. 321–330. doi:10.1145/1806689.1806735
Paolini, E.; Stepanov, E. (2012). «Existence and regularity results for the Steiner problem» (PDF). Calc. Var. Partial Diff. Equations. 46 (3–4): 837–860. doi:10.1007/s00526-012-0505-4. hdl:2158/600141
Robins, Gabriel; Zelikovsky, Alexander (2000). «Improved Steiner Tree Approximation in Graphs». Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00). Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 770–779. ISBN 0-89871-453-2
Sherwani, Naveed A. (1993). Algorithms for VLSI Physical Design Automation. [S.l.]: Kluwer Academic Publishers. ISBN 9781475722192
Smith, J. M.; Winter, P. (1995). «Computational geometry and topological network design». In: Du, Ding-Zhu; Hwang, Frank. Computing in Euclidean geometry. Col: Lecture Notes Series on Computing. 4 2nd ed. River Edge, NJ: World Scientific Publishing Co. pp. 351–451. ISBN 981-02-1876-1
Takahashi, Hiromitsu; Matsuyama, Akira (1980). «An approximate solution for the Steiner problem in graphs». Math. Japonica. 24 (6): 573–577
Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8
Wu, Bang Ye; Chao, Kun-Mao (2004). «Capítulo 7». Spanning Trees and Optimization Problems. [S.l.]: Chapman & Hall/CRC. ISBN 1-58488-436-3
Wu, Y. F.; Widmayer, P.; Wong, C. K. (maio de 1986). «A faster approximation algorithm for the Steiner problem in graphs». Acta Informatica. 23 (2): 223–229. doi:10.1007/bf00289500

Links Externos

O Commons possui uma categoria com imagens e outros ficheiros sobre Problema da árvore de Steiner

GeoSteiner (Software para resolver problema da árvore de Steiner euclidiana e retilinear; código fonte disponível, gratuito para uso não comercial)
SCIP-Jack (Software para resolver o problema da árvore de Steiner em grafos e 14 variantes, por exemplo, problema da árvore de Steiner para coleta de prêmios; gratuito para uso não comercial)
Fortran subroutine para encontrar o vértice de Steiner de um triângulo (isto é, Ponto de Fermat), suas distâncias dos vértices do triângulo e os pesos relativos dos vértices.
Phylomurka (Solucionador para o problema da árvore de Steiner em redes)
Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017), «Using Steiner Trees to Minimize Average Completion Times of Bulk Data Transfers», DCCast: Efficient Point to Multipoint Transfers Across Datacenters, USENIX Association, arXiv:1707.02096
M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems

[FOOTNOTERehfeldtKoch2023-1] Rehfeldt & Koch (2023).

[FOOTNOTEJuhlWarmeWinterZachariasen2018-2] Juhl et al. (2018).

[3] Korte, Bernhard; Nešetřil, Jaroslav (2001). «Vojtěch Jarnik's work in combinatorial optimization». Discrete Mathematics. 235 (1–3): 1–17. MR 1829832. doi:10.1016/S0012-365X(00)00256-9. hdl:10338.dmlcz/500662

[FOOTNOTECrescenziKannHalldórssonKarpinski2000-4] Crescenzi et al. (2000).

[FOOTNOTESherwani1993228-5] Sherwani (1993), p. 228.

[6] Ljubić, Ivana (2021). «Solving Steiner trees: Recent advances, challenges, and perspectives». Networks (em inglês). 77 (2): 177–204. ISSN 1097-0037. doi:10.1002/net.22005

[7] Novak, Roman; Rugelj, Joz̆e; Kandus, Gorazd (1 de outubro de 2001). «A note on distributed multicast routing in point-to-point networks». Computers & Operations Research (em inglês). 28 (12): 1149–1164. ISSN 0305-0548. doi:10.1016/S0305-0548(00)00029-0

[8] Klimm, Florian; Toledo, Enrique M.; Monfeuga, Thomas; Zhang, Fang; Deane, Charlotte M.; Reinert, Gesine (2 de novembro de 2020). «Functional module detection through integration of single-cell RNA sequencing data with protein–protein interaction networks». BMC Genomics. 21 (1). 756 páginas. ISSN 1471-2164. PMC 7607865. PMID 33138772. doi:10.1186/s12864-020-07144-2

[FOOTNOTEVazirani200327–28-9] Vazirani (2003), pp. 27–28.

[FOOTNOTEByrkaGrandoniRothvoßSanita2010-10] Byrka et al. (2010).

[FOOTNOTEChlebíkChlebíková2008-11] Chlebík & Chlebíková (2008).

[FOOTNOTEBermanKarpinskiZelikovsky2009-12] Berman, Karpinski & Zelikovsky (2009).

[FOOTNOTEKarpinskiZelikovsky1998-13] Karpinski & Zelikovsky (1998).

[FOOTNOTESmithWinter1995361-14] Smith & Winter (1995), p. 361.

[15] Kerivin, Hervé; Mahjoub, A. Ridha (2005). «Design of Survivable Networks: A survey». Networks (em inglês). 46 (1): 1–21. ISSN 0028-3045. doi:10.1002/net.20072

[FOOTNOTEPaoliniStepanov2012-16] Paolini & Stepanov (2012).

[FOOTNOTEKouMarkowskyBerman1981-17] Kou, Markowsky & Berman (1981).

[FOOTNOTETakahashiMatsuyama1980-18] Takahashi & Matsuyama (1980).

[FOOTNOTEWuWidmayerWong1986-19] Wu, Widmayer & Wong (1986).

[FOOTNOTERobinsZelikovsky2000-20] Robins & Zelikovsky (2000).

[FOOTNOTEDreyfusWagner1971-21] Dreyfus & Wagner (1971).

[FOOTNOTELevin1971-22] Levin (1971).

[FOOTNOTEFuchsKernMölleRichter2007-23] Fuchs et al. (2007).

[FOOTNOTEBjörklundHusfeldtKaskiKoivisto2007-24] Björklund et al. (2007).

[FOOTNOTELokshtanovNederlof2010-25] Lokshtanov & Nederlof (2010).

[FOOTNOTEFominKaskiLokshtanovPanolan2015-26] Fomin et al. (2015).

[FOOTNOTECyganDellLokshtanovMarx2016-27] Cygan et al. (2016).

[FOOTNOTEDomLokshtanovSaurabh2014-28] Dom, Lokshtanov & Saurabh (2014).

[FOOTNOTEGanley2004-29] Ganley (2004).

[30] The New York Times, 30 de outubro de 1990, reportou que uma prova foi encontrada, e que Ronald Graham, quem ofereceu 500 dólares pela prova, estava prestes a enviar um cheque aos autores.

[FOOTNOTEIvanovTuzhilin2012-31] Ivanov & Tuzhilin (2012).

[FOOTNOTEChungGraham1985-32] Chung & Graham (1985).

[FOOTNOTEHwang1976-33] Hwang (1976).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]