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.
No takes yet. Share an insight, caveat, or question.
Caccetta et al. (2001) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: