Approximation algorithm for the minimum directed tree cover

DOI10.1007/978-3-642-17461-2_12MaRDI QIDQ3066452zbMATH OpenOpenAlexFDO

Authors Viet Hung Nguyen

Publication date 10 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.3668

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Integer programming (90C10)

Abstract: 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 $max2,ln(D^{+})$ with $D^{+}$ is the maximum outgoing degree of the nodes in $G$.

Recommendations

• A 2log2(n)-Approximation Algorithm for Directed Tour Cover
• Approximating the minimum tour cover of a digraph
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Approximation Algorithms for Directed Steiner Problems

Cited in

(6)

• Finding minimum cost directed trees with demands and capacities
• Optimal direct and indirect covering trees
• Approximating the minmax rooted-tree cover in a tree
• How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover
• The Minimum Weight In-Tree Cover Problem
• A 2log2(n)-Approximation Algorithm for Directed Tour Cover

This page was built for publication: Approximation algorithm for the minimum directed tree cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3066452)