Approximating the minimum tour cover of a digraph

DOI10.3390/A4020075zbMATH Open1461.90161OpenAlexW2004947445MaRDI QIDQ1736480FDOQ1736480

Authors Viet Hung Nguyen

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmgraph algorithmpacking and coveringtree covertour cover

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 432785 (Why is no real title available?)
• 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
• 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)

• Approximating the Minimum Tour Cover with a Compact Linear Program
• Approximation algorithm for the minimum directed tree cover
• 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)