Approximating the tree and tour covers of a graph

Esther M. Arkin; Magnús M. Halldórsson; Rafael Hassin

doi:10.1016/0020-0190(93)90072-H

Approximating the tree and tour covers of a graph

Esther M. Arkin
, Magnús M. Halldórsson
, Rafael Hassin

Applied Mathematics and Statistics

Japan Advanced Institute of Science and Technology
Tel Aviv University

Research output: Contribution to journal › Article › peer-review

70 Scopus citations

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 from 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.

Original language	English
Pages (from-to)	275-282
Number of pages	8
Journal	Information Processing Letters
Volume	47
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(93)90072-H
State	Published - Oct 18 1993

Keywords

Algorithms
analysis of algorithms
combinatorial problems

Access to Document

10.1016/0020-0190(93)90072-H

Cite this

@article{be3ecd1b124044e2a5dfbd97b724b1e5,

title = "Approximating the tree and tour covers of a graph",

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 from 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.",

keywords = "Algorithms, analysis of algorithms, combinatorial problems",

author = "Arkin, \{Esther M.\} and Halld{\'o}rsson, \{Magn{\'u}s M.\} and Rafael Hassin",

year = "1993",

month = oct,

day = "18",

doi = "10.1016/0020-0190(93)90072-H",

language = "English",

volume = "47",

pages = "275--282",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "6",

}

TY - JOUR

T1 - Approximating the tree and tour covers of a graph

AU - Arkin, Esther M.

AU - Halldórsson, Magnús M.

AU - Hassin, Rafael

PY - 1993/10/18

Y1 - 1993/10/18

N2 - The tree and tour cover problems on an edge-weighted graph are to compute a minimum weight tree and closed walk, respectively, whose vertices from 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.

AB - The tree and tour cover problems on an edge-weighted graph are to compute a minimum weight tree and closed walk, respectively, whose vertices from 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.

KW - Algorithms

KW - analysis of algorithms

KW - combinatorial problems

UR - https://www.scopus.com/pages/publications/0027678734

U2 - 10.1016/0020-0190(93)90072-H

DO - 10.1016/0020-0190(93)90072-H

M3 - Article

AN - SCOPUS:0027678734

SN - 0020-0190

VL - 47

SP - 275

EP - 282

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Approximating the tree and tour covers of a graph

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this