<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>7369</REFNUM><AUTHORS><AUTHOR>Duckworth,W.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Zito,M.</AUTHOR></AUTHORS><YEAR>2005</YEAR><TITLE>On the approximability of the maximum induced matching problem</TITLE><PLACE_PUBLISHED>Journal of Discrete Algorithms, volume 3, no. 1</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>79-91</PAGES><ISBN>1570-8667</ISBN><LABEL>Duckworth:2005:7369</LABEL><KEYWORDS><KEYWORD>Induced matching; Strong matching; Regular graph; Approximation algorithm; APX-completeness</KEYWORD></KEYWORDS<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.</ABSTRACT><URL>http://dx.doi.org/10.1016/j.jda.2004.05.001</URL></RECORD></RECORDS></XML>