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 That Guy, From That Show! (talk | contribs) at 13:42, 26 February 2006 (migrate {{book reference}} to {{cite book}} using AWB). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.


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?

References

  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0716710455. A2.1: ND3, pg.206.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimum_routing_cost_spanning_tree&oldid=41312073"