Jump to content

Minimum routing cost spanning tree

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 84.59.113.235 (talk) at 16:41, 30 October 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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?

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