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