求解度约束最小生成树的新的快速算法

• 作者: 刘红卫 王立东 陈宏钦
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 度约束 生成树 算法
• 年，卷（期）: 2008,（31）
• 所属期刊栏目: 理论研究
• 页码范围: 51-52,56
• 页数: 3页
• 分类号: TP301
• 字数: 3224字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008.31.014

摘要

针对度约束最小生成树问题,提出了一种新的快速算法.新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树.第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顸点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中.通过大量的数值实验表明新的快速算法性能良好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘红卫	西安电子科技大学理学院	63	222	8.0	12.0
2	王立东	西安电子科技大学理学院	1	1	1.0	1.0
3	陈宏钦	西安电子科技大学理学院	1	1	1.0	1.0