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

Approximating the Directed Minimum Degree Spanning Tree of Directed Acyclic Graph

作　　者：姚国辉[1] 朱大铭[1] 马绍汉[1] 

机构地区：[1]山东大学计算机科学与技术学院,济南250061

出　　处：《计算机研究与发展》2009年第6期1052-1057,共6页Journal of Computer Research and Development

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

摘　　要：计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过Δ*+1,其中Δ*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.Given a directed acyclic graph G= （V,E） with n vertices and a root vertex r∈ V, the problem of constructing a spanning tree rooted at r whose maximal degree is the smallest among all spanning trees of G rooted at r is considered. An iterative polynomial time approximation algorithm for the problem is given. The algorithm computes a tree whose maximal degree is at most △＊＋ 1, where △＊ is the degree of some optimal tree for the problem. The running time of the algorithm is shown to be O（n^2 log n）, where n is the number of vertices. The algorithm does not employ any exhaustive enumeration, and its actual running time is likely to he much smaller in practice. Computing low degree trees is a fundamental problem in computer science, and it has many applications. For example, on the Internet there are a large amount of mails and news, which need to be broadcast among the sites. One of the parameters that different sites may want to reduce is the amount of work done by their site. Broadcasting information on a minimum degree spanning tree is such a solution. The problem is also intuitively appealing due to its seeming simplicity.

关 键 词：有向无环图 生成树 近似算法 最小度 优化 

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