The Directed Minimum-Degree Spanning Tree Problem

摘要

Consider a directed graph G = (V, E) with n vertices and a root vertex r ∈ V. The DMDST problem for G is one of constructing a spanning tree rooted at r, whose maximal degree is the smallest among all such spanning trees. The problem is known to be NP-hard. A quasi-polynomial time approximation algorithm for this problem is presented. The algorithm finds a spanning tree whose maximal degree is at most O(Δ~* + log n) where,Δ~* is the degree of some optimal tree for the problem. The running time of the algorithm is shown to be O(n~(O(log n)). Experimental results are presented showing that the actual running time of the algorithm is much smaller in practice.