IEICE TRANSACTIONS on Information
Approximated Vertex Cover for Graphs with Perfect Matchings
Summary :
Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.8 pp.2405-2410
- Publication Date
- 2006/08/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.8.2405
- Type of Manuscript
- Special Section INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tomokazu IMAMURA, Kazuo IWAMA, Tatsuie TSUKIJI, "Approximated Vertex Cover for Graphs with Perfect Matchings" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 8, pp. 2405-2410, August 2006, doi: 10.1093/ietisy/e89-d.8.2405.
Abstract: Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.8.2405/_p
Copy
@ARTICLE{e89-d_8_2405,
author={Tomokazu IMAMURA, Kazuo IWAMA, Tatsuie TSUKIJI, },
journal={IEICE TRANSACTIONS on Information},
title={Approximated Vertex Cover for Graphs with Perfect Matchings},
year={2006},
volume={E89-D},
number={8},
pages={2405-2410},
abstract={Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069
keywords={},
doi={10.1093/ietisy/e89-d.8.2405},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - Approximated Vertex Cover for Graphs with Perfect Matchings
T2 - IEICE TRANSACTIONS on Information
SP - 2405
EP - 2410
AU - Tomokazu IMAMURA
AU - Kazuo IWAMA
AU - Tatsuie TSUKIJI
PY - 2006
DO - 10.1093/ietisy/e89-d.8.2405
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2006
AB - Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069
ER -
English
