求解度约束最小生成树的一种改进算法

摘要

度约束最小生成树问题是网络设计和优化中的一个NP-hard问题.提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法.算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析.最后通过与其他算法的仿真比较,表明新算法的有效性和通用性.%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.