Approximating the minimum tour cover of a digraph

DOI10.3390/A4020075MaRDI QIDQ1736480zbMATH OpenOpenAlexFDO

Authors Viet Hung Nguyen

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a4020075

zbMATH Keywords

approximation algorithmgraph algorithmpacking and coveringtour covertree cover

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Review text

Summary: Given a directed graph \(G\) with non-negative cost on the arcs, a directed tour cover \(T\) of \(G\) is a cycle (not necessarily 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, in our knowledge, the DToCP remains widely open. In this paper, we give a \(2\log_2(n)\)-approximation algorithm for the DToCP.

Recommendations

• Approximating the tree and tour covers of a graph
• Approximating the Minimum Tour Cover with a Compact Linear Program
• Approximating the Minimum Equivalent Digraph
• scientific article; zbMATH DE number 1003248
• An approximation of the minimum vertex cover in a graph
• scientific article; zbMATH DE number 1788255
• On the Complexity of Finding a Minimum Cycle Cover of a Graph
• scientific article; zbMATH DE number 1033814
• scientific article; zbMATH DE number 5631194
• scientific article; zbMATH DE number 1463390

Cites work

• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Approximating the asymmetric profitable tour
• Approximating the tree and tour covers of a graph
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• scientific article; zbMATH DE number 432785 (Why is no real title available?)
• Improved approximations for tour and tree covers
• On some connectivity properties of Eulerian graphs
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs

Cited in

(5)

• Approximation algorithm for the minimum directed tree cover
• Approximating the Minimum Tour Cover with a Compact Linear Program
• A 2log2(n)-Approximation Algorithm for Directed Tour Cover
• Approximating the tree and tour covers of a graph
• The indefinite period traveling salesman problem

This page was built for publication: Approximating the minimum tour cover of a digraph

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