Minimum routing cost spanning tree
In computer science, the minimum routing cost spanning tree of a weighted graph is a spanning tree minimizing the sum of pairwise distances between vertices in the tree. It is also called the shortest total path length spanning tree, minimum total distance spanning tree, or minimum average distance spanning tree.
It is NP-hard to construct it, even for unweighted graphs.[1][2] However, it has a polynomial-time approximation scheme. The approximation works by choosing a number that depends on the approximation ratio but not on the number of vertices of the input graph, and by searching among all trees with internal nodes.[3]
In an unweighted graph, this is the spanning tree of minimum Wiener index.[4]
References
- ^ Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1978). "The complexity of the network design problem". Networks. 8 (4): 279–285. doi:10.1002/net.3230080402. MR 0514463.
- ^ Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.1: ND3, pg.206.
- ^ Wu, Bang Ye; Lancia, Giuseppe; Bafna, Vineet; Chao, Kun-Mao; Ravi, R.; Tang, Chuan Yi (2000). "A polynomial-time approximation scheme for minimum routing cost spanning trees". SIAM Journal on Computing. 29 (3): 761–778. doi:10.1137/S009753979732253X. MR 1740574.
- ^ Dobrynin, Andrey A.; Entringer, Roger; Gutman, Ivan (2001). "Wiener index of trees: theory and applications". Acta Applicandae Mathematicae. 66 (3): 211–249. doi:10.1023/A:1010767517079. MR 1843259.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |