Covering Graphs using Trees and Stars

trees such that their union includes all the vertices of $G$. The cost
of a tree cover is the weight of the maximum weight tree in the tree
cover. Given a positive integer $k$, the $k$-tree cover problem is to
compute a minimum cost tree cover which has no more than $k$
trees. Star covers are defined analogously. Additionally, we may also
be provided with a set of $k$ vertices which are to serve as roots of
the trees or stars. In this paper, we provide constant factor
approximation algorithms for finding tree and star covers of graphs,
in the rooted and un-rooted versions.

Joint work with Naveen Garg, Jochen Koenemann, R. Ravi, and Amitabh Sinah.
This paper will be presented in APPROX-03.