Minimum routing cost spanning tree

This article may meet Wikipedia's criteria for speedy deletion as a very short article lacking sufficient context to identify the subject of the article. See CSD A1.

If this article does not meet the criteria for speedy deletion, or you intend to fix it, please remove this notice, but do not remove this notice from pages that you have created yourself. If you created this page and you disagree with the given reason for deletion, you can click the button below and leave a message explaining why you believe it should not be deleted. You can also visit the talk page to check if you have received a response to your message.

Note that this article may be deleted at any time if it unquestionably meets the speedy deletion criteria, or if an explanation posted to the talk page is found to be insufficient.

Nominator: Please consider placing the template:

{{subst:Db-nocontext-notice|Minimum routing cost spanning tree|header=1}} ~~~~

on the talk page of the author.

Note to administrators: this article has content on its talk page which should be checked before deletion.

Administrators: check links, talk, history (last), and logs before deletion. Consider checking Google.
This page was last edited by Propaniac (contribs | logs) at 14:30, 15 June 2007 (UTC) (18 years ago)

This article may require cleanup to meet Wikipedia's quality standards. No cleanup reason has been specified. Please help improve this article if you can. (December 2006) (Learn how and when to remove this message)

Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation.

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.