%0 Journal Article
%T A new algorithm for degree-constrained minimum spanning tree based on the reduction technique<br>
%A Aibing Ning
%A Liang M
%A Xiaohua Xiong
%A <br>
%J 自然科学进展
%D 2008
%I 
%X The degree-constrained minimum spanning tree (DCMST) is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been pre-processed by reduction algorithm.
%K degree-constrained minimum spanning tree
%K reduction algorithm
%K edge exchange technique
%K combinatorial optimization<br>
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=01BA20E8BA813E1908F3698710BBFEFEE816345F465FEBA5&cid=96E6E851B5104576C2DD9FC1FBCB69EF&jid=504AF8C1E5476CA7C4EC9DF6FEAC14AC&aid=63D10EF6AB1BEE62C291E3B915101357&yid=67289AFF6305E306&vid=13553B2D12F347E8&iid=E158A972A605785F&sid=DDDA4F26E8AD3C0E&eid=A03A15CF5604A8B0&journal_id=1002-008X&journal_name=自然科学进展&referenced_num=0&reference_num=0