A branch and cut method for the degree-constrained minimum spanning tree problem

Abstract

A problem of interest in network design is that of finding, in a given weighted graph, a minimum-weight spanning tree whose vertices satisfy specified degree restrictions. We present a branch and cut solution procedure for this NP-complete problem. Our algorithm is implemented and extensively tested. Computational results on 3150 random table problems ranging from 100 to 800 vertices are presented and discussed. © 2001 John Wiley & Sons, Inc.