有向无环图最小度生成树问题的一种近似算法

作     者：姚国辉 朱大铭 马绍汉 Yao Guohui;Zhu Daming;Ma Shaohan

作者机构：山东大学计算机科学与技术学院济南250061 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2009年第46卷第6期

页      面：1052-1057页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(60573024) 山东省科技攻关基金项目 

主　　题：有向无环图 生成树 近似算法 最小度 优化 

摘      要：计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过Δ*+1,其中Δ*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.