Capacitated minimum spanning tree information

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. 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 $c$ . The edges connecting the subgraphs to the root node are called gates. Finding the optimal solution is NP-hard.^[1]

^ Jothi, Raja; Raghavachari, Balaji (2005), "Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design", ACM Trans. Algorithms, 1 (2): 265–282, doi:10.1145/1103963.1103967, S2CID 8302085

[1] Jothi, Raja; Raghavachari, Balaji (2005), "Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design", ACM Trans. Algorithms, 1 (2): 265–282, doi:10.1145/1103963.1103967, S2CID 8302085

Capacitated minimum spanning tree information

and 6 Related for: Capacitated minimum spanning tree information

Minimum spanning tree

Capacitated minimum spanning tree

List of terms relating to algorithms and data structures

Column generation

Ant colony optimization algorithms

Siamese fighting fish