Capacitated minimum spanning tree
Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node and satisfies the capacity constraint . The capacity constraint ensures that all subtrees (maximal subgraphs connected to the root by a single edge) incident on the root node have no more than nodes. If the tree nodes have weights, then the capacity constraint may be interpreted as follows: the sum of weights in any subtree should be no greater than . The edges connecting the subgraphs to the root node are called gates. Finding the optimal solution is NP-hard.
Wikipage disambiguates
primaryTopic
Capacitated minimum spanning tree
Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node and satisfies the capacity constraint . The capacity constraint ensures that all subtrees (maximal subgraphs connected to the root by a single edge) incident on the root node have no more than nodes. If the tree nodes have weights, then the capacity constraint may be interpreted as follows: the sum of weights in any subtree should be no greater than . The edges connecting the subgraphs to the root node are called gates. Finding the optimal solution is NP-hard.
has abstract
Capacitated minimum spanning t ...... e optimal solution is NP-hard.
@en
Wikipage page ID
23,015,254
Wikipage revision ID
702,633,175
subject
comment
Capacitated minimum spanning t ...... e optimal solution is NP-hard.
@en
label
Capacitated minimum spanning tree
@en