Balanced spanning forests and trees

This work addresses spanning forests and trees in which the number of nodes in component subtrees is balanced. The solution procedure developed makes use of Lagrangean relaxation and heuristics. Dual‐ascent procedures in conjunction with heuristics are used to yield lower and upper bounds. Computational experience indicates that optimal or suboptimal solutions with very tight bounds can be obtained in 180 to 300 iterations on the average for 100‐node balanced tree problems and 700 to 1400 iterations for 100‐node balanced forest problems.