abstract: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 constraint 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.
The capacitatedminimumspanningtreeproblem (CMST), oneof the mostfundamentalproblemsintelecommunicationsand in the optimaldesign of networks, is studied.