Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Approximation Algorithm for the Minimum Directed Tree Cover
verfasst von : Viet Hung Nguyen
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
.