The minimum spanning tree problem with an added constraint that no node in the spanning tree has the degree more than a specified integer d, is known as the degree-constrained minimum spanning tree problem. Finding the degree-constrained minimum spanning tree of a graph is a well-studied NP-hard problem. This paper presents an effective ant-based algorithm for the degree-constrained minimum spanning tree problem. Experimental results on a benchmark set of problem instances show that the algorithm performs very well against previous algorithms.
展开▼
