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 Dcoetzee (talk | contribs) at 08:21, 27 November 2005 (Add NP Guide ref). 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

  • . ISBN 0716710455. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help) A2.1: ND3, pg.206.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimum_routing_cost_spanning_tree&oldid=29362696"