Article ID Journal Published Year Pages File Type
10333110 Journal of Discrete Algorithms 2005 13 Pages PDF
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
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
On the approximability of the maximum induced matching problem
Authors
, , ,