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

【Abstract】 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(n2logn),where n is the number of vertices. The algorithm does not employ any exhaustive enumeration,and its actual running time is likely to be 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.更多还原