UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 7369

On the approximability of the maximum induced matching problem
Duckworth,W. Manlove,D.F. Zito,M.

Publication Type: Journal
Appeared in: Journal of Discrete Algorithms, volume 3, no. 1
Page Numbers : 79-91
Publisher: Elsevier Science
Year: 2005
ISBN/ISSN: 1570-8667

URL: This publication is available at this URL.

Abstract:

In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d-1 for MIM in d-regular graphs, for each d>=3. We also prove that MIM is APX-complete in d-regular graphs, for each d>=3.

Keywords: Induced matching; Strong matching; Regular graph; Approximation algorithm; APX-completeness


PDF Bibtex entry Endnote XML