An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs

Yuichi ASAHIRO  Guohui LIN  Zhilong LIU  Eiji MIYANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1142-1149
Publication Date: 2019/09/01
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
Keyword: 
induced matching problem,  C5-free regular graph,  approximation algorithm,  

Full Text: PDF(1.4MB)>>
Buy this Article



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.