Algorithms for degree-constrained Euclidean Steiner minimal tree  

作　　者：Zhang Jin Ma Liang Zhang Liantang 

机构地区：[1]School of Management, Univ. of Shanghai for Science and Technology, Shanghai 200093, P. R. China [2]Computer and Information Engineering Coll., Univ. of Henan, Kaifeng 475001, P. R. China

出　　处：《Journal of Systems Engineering and Electronics》2008年第4期735-741,共7页系统工程与电子技术（英文版）

基　　金：the National Natural Science Foundation of China (70471065);the Shanghai Leading Academic Discipline Project (T0502).

摘　　要：A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.

关 键 词：DEGREE-CONSTRAINED Euclidean Steiner minimal tree simulated annealing ant algorithm 

分 类 号：O224[理学—运筹学与控制论] O178[理学—数学]