| Article ID: | iaor20023418 |
| Country: | United States |
| Volume: | 37 |
| Issue: | 2 |
| Start Page Number: | 74 |
| End Page Number: | 83 |
| Publication Date: | Mar 2001 |
| Journal: | Networks |
| Authors: | Caccetta L., Hill S.P. |
| Keywords: | programming: integer |
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.