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 SmackBot (talk | contribs) at 21:21, 13 January 2007 (Date/fix the maintenance tags using AWB). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

You must add a |reason= parameter to this Cleanup template – replace it with {{Cleanup|December 2006|reason=<Fill reason here>}}, or remove the Cleanup template.



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 0-7167-1045-5. A2.1: ND3, pg.206.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimum_routing_cost_spanning_tree&oldid=100514558"