Capacitated minimum spanning tree

<p>Capacitated minimum spanning tree is a minimal cost <a href="/facts/Spanning_tree_(mathematics)/qQPN9taR">spanning tree</a> of a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> that has a designated root node 
  
    
      
        r
      
    
    {\displaystyle r}
  
 and satisfies the capacity constraint 
  
    
      
        c
      
    
    {\displaystyle c}
  
. The capacity constraint ensures that all subtrees (maximal subgraphs connected to the root by a single edge) incident on the root node 
  
    
      
        r
      
    
    {\displaystyle r}
  
 have no more than 
  
    
      
        c
      
    
    {\displaystyle 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
      
    
    {\displaystyle c}
  
. The edges connecting the subgraphs to the root node are called <i>gates</i>. Finding the <a href="/facts/Optimal_solution/QzwJfFEE">optimal solution</a> is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>.
</p>

Capacitated minimum spanning tree open-in-new

Capacitated minimum spanning tree