计算机应用与软件2012，Vol.29Issue(5)：48-49,80,3.
求解度约束最小生成树的一种改进算法
AN IMPROVED ALGORITHM FOR FINDING DEGREE CONSTRAINED MINIMUM SPANNING TREE
摘要
Abstract
The degree-constrained minimum spanning tree issue is an NP-hard problem in network design and optimisation. An improved algorithm for finding minimum spanning tree of a specified node with maximum degree constraint in network G is presented in this paper. On the premise of warranting the maximum degree of the specified node, this algorithm gets the minimum spanning tree of the specified node with maximum degree constraint in network G by adding into current network the selected edge with minimum weight in residuals. At the same time, the complexity of the new algorithm has been analysed as well. The validity and the universality of the new algorithm are shown through the simulative comparison with other algorithms at last.关键词
最大度/度约束/改进算法/最小生成树Key words
Maximum degree/ Degree constraint/ Improved algorithm/ Minimum spanning tree分类
信息技术与安全科学引用本文复制引用
贾青慧..求解度约束最小生成树的一种改进算法[J].计算机应用与软件,2012,29(5):48-49,80,3.基金项目
国家自然科学基金项目(10574059) （10574059）
甘肃省自然科学项目(0710RJZA072). （0710RJZA072）
