A fast algorithm for Steiner trees
作者： L. Kou , G. Markowsky , L. Berman
DOI: 10.1007/BF00288961
关键词:
摘要: … all Steiner trees for G and S. The problem of finding a minimal Steiner tree for any given G and … Given any spanning tree in G 1, we can construct a subgraph of G by replacing each edge …
acm.org
mst.edu
springer.com
sci-hub.se 
maine.edu 参考文章(9)
Andrew Chi-chih Yao, An 0(|E|loglog|V|) algorithm for finding minimum spanning trees☆ Information Processing Letters. ,vol. 4, pp. 21- 23 ,(1975) , 10.1016/0020-0190(75)90056-3
Robert W. Floyd, Algorithm 97: Shortest path Communications of The ACM. ,vol. 5, pp. 345- ,(1962) , 10.1145/367766.368168
M. R. Garey, R. L. Graham, D. S. Johnson, Some NP-complete geometric problems Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76. pp. 10- 22 ,(1976) , 10.1145/800113.803626
F. K. Hwang, On Steiner Minimal Trees with Rectilinear Distance Siam Journal on Applied Mathematics. ,vol. 30, pp. 104- 114 ,(1976) , 10.1137/0130013
Yves Tabourier, All shortest distances in a graph. An improvement to Dantzig's inductive algorithm Discrete Mathematics. ,vol. 4, pp. 83- 87 ,(1973) , 10.1016/0012-365X(73)90118-0
E. N. Gilbert, H. O. Pollak, Steiner Minimal Trees SIAM Journal on Applied Mathematics. ,vol. 16, pp. 1- 29 ,(1968) , 10.1137/0116001
David Cheriton, Robert Endre Tarjan, Finding Minimum Spanning Trees SIAM Journal on Computing. ,vol. 5, pp. 724- 742 ,(1976) , 10.1137/0205051
E. W. Dijkstra, A note on two problems in connexion with graphs Numerische Mathematik. ,vol. 1, pp. 269- 271 ,(1959) , 10.1007/BF01386390
Richard M. Karp, Reducibility Among Combinatorial Problems. Complexity of Computer Computations. pp. 85- 103 ,(1972)