Abstract
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. © 2009 Springer Berlin Heidelberg.