Shortest total path length spanning tree
From Wikipedia, the free encyclopedia
 |
This article may require cleanup to meet Wikipedia's quality standards. Please discuss this issue on the talk page or replace this tag with a more specific message. This article has been tagged since December 2006. |
 |
Please help improve this article or section by expanding it. Further information might be found on the talk page or at requests for expansion. This article has been tagged since January 2007. |
Shortest total path length spanning tree
Input: n-node undirected graph G(V,E); positive integer B.
Question: Is there a spanning tree T(V,F) of G such that the sum over all pairs of nodes u and v of the length of the path between u and v in T is no greater than B?
[edit] References
- 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.
