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

New fast algorithm for degree-constrained minimum spanning tree problem

作　　者：王立东[1] 刘红卫[1] 陈宏钦[1] 

机构地区：[1]西安电子科技大学理学院,西安710071

出　　处：《计算机工程与应用》2008年第31期51-52,56,共3页Computer Engineering and Applications

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

关 键 词：度约束 生成树 算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]