Approximation to the Minimum Rooted Star Cover Problem

摘要

In this paper, we study the following minimum rooted star cover problem: given a complete graph G = (V, E) with a length function l : E → Z~+ that satisfies the triangle inequality, a designated root vertex r ∈ V, and a length bound D, the objective is to find a minimum cardinality set of rooted stars, that covers all vertices in V such that the length of each rooted star is at most D, where a rooted star is a subset of E having a common center s ∈ V and containing the edge (r, a). This problem is NP-complete and we present a constant ratio approximation algorithm for this problem.