Approximating the Tree and Tour Covers of a Graph

Esther Arkin

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

Refael Hassin

Abstract: The tree and tour cover problems on an edge-weighted graph are to compute a minimum weight tree and closed walk, respectively, whose vertices form a vertex cover. Both problems are NP-hard. In this note we give strongly polynomial time, constant factor approximation algorithms for both problems. An interesting feature of our algorithms is how they combine approximations of other problems, namely the weighted vertex cover, traveling salesman, and Steiner tree problems.