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

• 作者: 贾青慧
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 最大度 度约束 改进算法 最小生成树
• 年，卷（期）: 2012,（5）
• 所属期刊栏目: 基金项目论文
• 页码范围: 48-49,80
• 分类号: TP393
• 字数: 3159字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2012.05.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贾青慧		6	15	2.0	3.0