Fast approximation algorithm for the degree-constrained minimum spanning tree problem
Song Hai-zhou · Journal of systems engineering · 2006
A fast approximation algorithm for the degree-constrained minimum spanning tree problem is proposed in this paper.First,the kernel ideal of the fast approximation algorithm is given as follows: An edge that possesses minimal weight is added if the added edge will not disobey degree-constraint and will not form a circle.Second,the concrete steps of the fast approximation algorithm are presented.Furthermore,it is proved that the time complexity of the algorithm is polynomial function of the number of vertex,and the validity theorem of the algorithm is proved.Many numerical tests show that the fast approximation algorithm has very good performance.Finally,a fast approximation algorithm for traveling salesman problems is given.