Approximating the Minimum Tour Cover with a Compact Linear Program

DOI10.1007/978-3-319-06569-4_7zbMath1322.05131OpenAlexW23932788MaRDI QIDQ3192959

Viet Hung Nguyen

Publication date: 14 October 2015

Published in: Advanced Computational Methods for Knowledge Engineering (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-06569-4_7

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Graph covering using bounded size subgraphs

Cites Work

• Unnamed Item
• Approximating the tree and tour covers of a graph
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Improved approximations for tour and tree covers
• Worst-case analysis of a new heuristic for the travelling salesman problem
• How to trim a MST
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

This page was built for publication: Approximating the Minimum Tour Cover with a Compact Linear Program