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

摘要：

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

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

所属期刊栏目：44

分类号：TP301(计算技术、计算机技术)

在线出版日期：2008-12-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：51-52,56