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.