| dc.description.abstract | Most network design problems are computationally intractable. For obtaining approximations, greedy heuristics are commonly employed. The Esau-Williams algorithm adopts a better greedy heuristic in solving (constrained) capacitated minimum spanning tree (CMST) problem, using a tradeoff function computing the potential saving in the cost of a link. In this study, the component-oriented tradeoff computation was employed instead of the node-oriented one to implement the heuristic efficiently. The improved Esau-Williams algorithm was modified for variations of the CMST problems with order, degree, and depth constraints. In the problems, a common operation was to check if accepting the link could satisfy the constraint. In the weight- and the order-constraint problems, once accepting the link would fail to satisfy the constraint, the link can be discarded. In the degree- and the depth-constraint problems, however, some links have possibility to be accepted later even though accepting them would violate the constraint at the moment. While the heuristic for the depth constraint presented in this study may be overcome by other alternative approaches, decision of accepting the link can be made when the relation between the connected components is analyzed. Thus, this improved Esau-Williams algorithm can be used as the basic algorithm for designing local access networks. | |
