| 求解度约束最小生成树的一种改进算法 |
| |
| 引用本文： | 贾青慧. 求解度约束最小生成树的一种改进算法[J]. 计算机应用与软件, 2012, 29(5): 48-49,80 |
| |
| 作者姓名： | 贾青慧 |
| |
| 作者单位： | 兰州资源环境职业技术学院 甘肃 兰州 730021 |
| |
| 基金项目： | 国家自然科学基金项目，甘肃省自然科学项目 |
| |
| 摘 要： | 度约束最小生成树问题是网络设计和优化中的一个NP-hard问题。提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法。算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较,表明新算法的有效性和通用性。
|
| 关 键 词： | 最大度 度约束 改进算法 最小生成树 |
AN IMPROVED ALGORITHM FOR FINDING DEGREE CONSTRAINED MINIMUM SPANNING TREE |
| |
| Jia Qinghui. AN IMPROVED ALGORITHM FOR FINDING DEGREE CONSTRAINED MINIMUM SPANNING TREE[J]. Computer Applications and Software, 2012, 29(5): 48-49,80 |
| |
| Authors: | Jia Qinghui |
| |
| Affiliation: | Jia Qinghui(Lanzhou Resources and Environment Voc-Tech College,Lanzhou 730021,Gansu,China) |
| |
| 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. |
| |
| Keywords: | Maximum degree Degree constraint Improved algorithm Minimum spanning tree |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
