Premium
A branch and cut method for the degree‐constrained minimum spanning tree problem
Author(s) -
Caccetta L.,
Hill S.P.
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200103)37:2<74::aid-net2>3.0.co;2-e
Subject(s) - minimum spanning tree , spanning tree , degree (music) , branch and cut , minimum degree spanning tree , distributed minimum spanning tree , mathematics , mathematical optimization , tree (set theory) , branch and bound , kruskal's algorithm , combinatorics , computer science , integer programming , physics , acoustics
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.