APPROXIMATING THE TREE AND TOUR COVERS OF A GRAPH

Authors
ARKIN EM HALLDORSSON MM HASSIN R
Citation
Em. Arkin et al., APPROXIMATING THE TREE AND TOUR COVERS OF A GRAPH, Information processing letters, 47(6), 1993, pp. 275-282
Citations number
23
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
47
Issue
6
Year of publication
1993
Pages
275 - 282
Database
ISI
SICI code
0020-0190(1993)47:6<275:ATTATC>2.0.ZU;2-B
Abstract
The tree and tour cover problems on an edge-weighted graph are to comp ute a minimum weight tree and closed walk, respectively, whose vertice s form a vertex cover. Both problems are NP-hard. In this note we give strongly polynomial time, constant factor approximation algorithms fo r both problems. An interesting feature of our algorithms is how they combine approximations of other problems, namely the weighted vertex c over, traveling salesman, and Steiner tree problems.