Approximating the Directed Minimum Degree Spanning Tree of Directed Acyclic Graph

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\+2logn), 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.