2009 | OriginalPaper | Chapter
A 2log2(n)-Approximation Algorithm for Directed Tour Cover
Author : Viet Hung Nguyen
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a directed graph
G
with non-negative cost on the arcs, a directed tour cover
T
of
G
is a cycle (not necessary simple) in
G
such that either head or tail (or both of them) of every arc in
G
is touched by
T
. The minimum directed tour cover problem (DToCP) which is to find a directed tour cover of minimum cost, is
NP
-hard. It is thus interesting to design approximation algorithms with performance guarantee to solve this problem. Although its undirected counterpart (ToCP) has been studied in recent years [1,6], in our knowledge, the DTCP remains widely open. In this paper, we give a 2log
2
(
n
)-approximation algorithm for the DTCP.