Abstract
A tree (tour) cover of an edge-weighted graph is a set of edges which forms a tree (closed walk) and covers every other edge in the graph. Arkin et al. give approximation algorithms with ratios 3.55 (tree cover) and 5.5 (tour cover). We present algorithms with a worst-case ratio of 3 for both problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Könemann, J., Konjevod, G., Parekh, O. et al. Improved Approximations for Tour and Tree Covers. Algorithmica 38, 441–449 (2004). https://doi.org/10.1007/s00453-003-1071-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-003-1071-0