Capacitated minimum spanning tree

Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node $r$ and satisfies the capacity constraint $c$. The capacity constrain ensures that all subtrees (maximal subgraphs connected to the root by a single edge) incident on the root node $r$ have no more than $c$ 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 $c$. To find the optimal solution, one has to go through all the possible spanning tree configurations for a given graph and pick the one with the lowest cost; such search requires an exponential number of computations.

Algorithms

Esau-Williams heuristic

Esau-Williams heuristic is based on the notion of a tradeoff:

Applications

CMST problem is important in network design: when many terminal computers have to be connected to the central hub, the star configuration is usually not the minimum cost design. Finding a CMST that organizes the terminals into subnetworks can lower the cost of implementing a network.