Approximating the Spanning k-Tree Forest Problem

摘要

As a generalization of the spanning star forest problem, the spanning k-tree forest problem is to find a maximum-edge-weight spanning forest in which each tree has a central node and other nodes in the tree are at most k-distance away from the central node. In this paper, we show that it can be approximated with ratio k/k+1- in polynomial time for both undirected and directed graphs. In the weighted distance model, a 0.5-approximation algorithm is presented.