Jump to content

Minimum routing cost spanning tree

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 07:28, 13 June 2019 (Looks adequately notable but needs a different title). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, the minimum total distance 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 minimum average distance spanning tree or minimum routing cost spanning tree. It is NP-hard to construct it.[1] However, it has a polynomial-time approximation scheme.[2]

References

  1. ^ 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.
  2. ^ 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.
Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimum_routing_cost_spanning_tree&oldid=901633580"