Approximating the minimum directed tree cover

Details Approximating the minimum directed tree cover Approximating the minimum directed tree cover

2010-04-21

arxiv.org/abs/1004.3668v3

Computer Science

Data Structures and Algorithms

13 pages

Scientific paper

Given a directed graph $G$ with non negative cost on the arcs, a directed tree cover of $G$ is a rooted directed tree such that either head or tail (or both of them) of every arc in $G$ is touched by $T$. The minimum directed tree cover problem (DTCP) is to find a directed tree cover of minimum cost. The problem is known to be $NP$-hard. In this paper, we show that the weighted Set Cover Problem (SCP) is a special case of DTCP. Hence, one can expect at best to approximate DTCP with the same ratio as for SCP. We show that this expectation can be satisfied in some way by designing a purely combinatorial approximation algorithm for the DTCP and proving that the approximation ratio of the algorithm is $\max\{2, \ln(D^+)\}$ with $D^+$ is the maximum outgoing degree of the nodes in $G$.

Affiliated with

Also associated with

No associations

Rating

Approximating the minimum directed tree cover does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating the minimum directed tree cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the minimum directed tree cover will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-326792