Shortest total path length spanning tree
From HandWiki
In computer science, the shortest total path length spanning tree is, given an n-node undirected graph G(V, E); positive integer B, does there exist 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?
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.
 |
