Shortest total path length spanning tree

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


This article is issued from Wikipedia - version of the 12/18/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.