A new algorithm for degree-constrained minimum spanning tree based on the reduction technique  

作　　者：Aibing Ning Liang Ma Xiaohua Xiong 

机构地区：[1]School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China [2]College of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, China

出　　处：《Progress in Natural Science:Materials International》2008年第4期495-499,共5页自然科学进展·国际材料（英文版）

基　　金：the National Natural Science Foundation of China（Grant No.70471065）;Shanghai Leading Academic Discipline Project（Grant No. T0502）;Shanghai Scientific Special Funds for Cultivation and Selection of Excel.lent Young Teaching Staffs of Higher Education（Grant No.21012）.

摘　　要：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 math- ematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the prob- lem. Also an algorithm for DCMST to solve the smaller problem is presented which has been preprocessed by reduction algorithm.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 preprocessed by reduction algorithm.

关 键 词：Degree-constrained minimum spanning tree Reduction algorithm Edge exchange technique Combinatorial optimization 

分 类 号：O14[理学—数学]