Balances Spanning Forests and Trees
Journal
Networks
Journal Volume
21
Journal Issue
6
Pages
667-687
Date Issued
1991
Author(s)
Agha Iqbal Ali
Abstract
Abstract 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.
SDGs
Type
journal article