Edge exchanges in the degree-constrained minimum spanning tree problem |
| |
Authors: | Martin Savelsbergh Ton Volgenant |
| |
Affiliation: | Faculty of Actuarial Science and Econometrics, University of Amsterdam, Holland Netherlands |
| |
Abstract: | We describe a branch and bound algorithm to solve the degree-constrained minimum spanning tree problem. We propose an edge exchange analysis frequently used in the algorithm and three types of heuristic methods. Computational results are reported for problems with up to 200 vertices. These results are much better than known results from the literature. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |