IEICE TRANSACTIONS on Fundamentals
An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs
Summary :
In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $left( rac{3d}{4}- rac{1}{8}+ rac{3}{16d-8} ight)$. In this paper, we design a $left( rac{2d}{3}+ rac{1}{3} ight)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1142-1149
- Publication Date
- 2019/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.1142
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Optimization
Authors
Yuichi ASAHIRO
Kyushu Sangyo University
Guohui LIN
University of Alberta
Zhilong LIU
Kyushu Insitute of Technology
Eiji MIYANO
Kyushu Insitute of Technology
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
Yuichi ASAHIRO, Guohui LIN, Zhilong LIU, Eiji MIYANO, "An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1142-1149, September 2019, doi: 10.1587/transfun.E102.A.1142.
Abstract: In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $left( rac{3d}{4}- rac{1}{8}+ rac{3}{16d-8}
ight)$. In this paper, we design a $left( rac{2d}{3}+ rac{1}{3}
ight)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1142/_p
Copy
@ARTICLE{e102-a_9_1142,
author={Yuichi ASAHIRO, Guohui LIN, Zhilong LIU, Eiji MIYANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs},
year={2019},
volume={E102-A},
number={9},
pages={1142-1149},
abstract={In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $left( rac{3d}{4}- rac{1}{8}+ rac{3}{16d-8}
ight)$. In this paper, we design a $left( rac{2d}{3}+ rac{1}{3}
ight)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6.},
keywords={},
doi={10.1587/transfun.E102.A.1142},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1142
EP - 1149
AU - Yuichi ASAHIRO
AU - Guohui LIN
AU - Zhilong LIU
AU - Eiji MIYANO
PY - 2019
DO - 10.1587/transfun.E102.A.1142
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $left( rac{3d}{4}- rac{1}{8}+ rac{3}{16d-8}
ight)$. In this paper, we design a $left( rac{2d}{3}+ rac{1}{3}
ight)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6.
ER -
English
