Jump to content

Capacitated minimum spanning tree

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Lynxoid84 (talk | contribs) at 16:33, 30 May 2009 (Created page with 'Capacitated minimum spanning tree is a variation of minimum spanning tree problem with a designated root node and a capacity constraint …'). 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)

Capacitated minimum spanning tree is a variation of minimum spanning tree problem with a designated root node and a capacity constraint that ensures that all subtrees incident to the root node have no more than nodes. If the tree nodes have weights, then the capacity constrain may be interpreted as follows: the sum of weights in any subtree should be no greater than .