Premium
Balanced spanning forests and trees
Author(s) -
Ali Agha Iqbal,
Huang ChungHsing
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210605
Subject(s) - heuristics , node (physics) , spanning tree , minimum spanning tree , mathematical optimization , relaxation (psychology) , tree (set theory) , computer science , mathematics , linear programming relaxation , component (thermodynamics) , combinatorics , linear programming , psychology , social psychology , structural engineering , engineering , physics , thermodynamics
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.