| 求解度约束最小生成树的新的快速算法 |
| |
| 引用本文： | 王立东,刘红卫,陈宏钦. 求解度约束最小生成树的新的快速算法[J]. 计算机工程与应用, 2008, 44(31). DOI: 10.3778/j.issn.1002-8331.2008.31.014 |
| |
| 作者姓名： | 王立东 刘红卫 陈宏钦 |
| |
| 作者单位： | 西安电子科技大学,理学院,西安,710071;西安电子科技大学,理学院,西安,710071;西安电子科技大学,理学院,西安,710071 |
| |
| 摘 要： | 针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树。第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顶点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中。通过大量的数值实验表明新的快速算法性能良好。
|
| 关 键 词： | 度约束 生成树 算法 |
New fast algorithm for degree-constrained minimum spanning tree problem |
| |
| WANG Li-dong,LIU Hong-wei,CHEN Hong-qin. New fast algorithm for degree-constrained minimum spanning tree problem[J]. Computer Engineering and Applications, 2008, 44(31). DOI: 10.3778/j.issn.1002-8331.2008.31.014 |
| |
| Authors: | WANG Li-dong LIU Hong-wei CHEN Hong-qin |
| |
| Abstract: | A new fast algorithm for the degree-constrained minimum spanning tree problem is proposed.The new algorithm consists of two major parts.The first part constructs a degree-constrained tree from a minimum spanning tree.The second part presents an improvement strategy.Based on the degree-constrained tree obtained from the first part,it removes one edge of the tree,as divides the vertices of the graph into two sets by connectivity.The added edge which doesn’t violate the degree-constraint and offers the maximum reduction in the weight of the tree is selected from the edge cut which is got by the two sets.Many numerical tests show that the new fast algorithm has very good performance. |
| |
| Keywords: | degree-constrained spanning tree algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
