A Lagrangean approach to the degree-constrained minimum spanning tree problem

A known branch and bound algorithm for the degree-constrained minimum spanning tree problem is adapted for the use of Lagrangean multipliers. They improve the bounds from which the edge elimination analysis is the algorithm benefits in particular. Computational results are given for problems up to 150 nodes both random drawn coordinate problems as well drawn table problems. These results are much better than other results reported in literature and they show the Lagrangean approach to be more effective when the problems are more difficult to solve.