求解度约束最小生成树问题的新算法

• 作者: 刘三阳 孙小军 王志强
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 度 度约束 最小生成树 第k最小生成树 最小k度生成树
• 年，卷（期）: 2010,（36）
• 页码范围: 40-42,47
• 分类号: TP301.6
• 字数: 3369字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.36.011

摘要

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小七度生成树的新算法.该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树.给出了算法实施的具体步骤,并证明了算法的正确性.最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘三阳	西安电子科技大学理学院	662	5562	32.0	51.0
2	孙小军	宝鸡文理学院数学系	57	242	9.0	11.0
3	王志强		9	32	4.0	5.0