Computability in Europe 2008
Logic and Theory of Algorithms
|Slot:||Wed, 17:10-17:30, Room 20 (col. 1)|
An induced matching is a matching $M$ where each two edges $e_1,\,e_2 \in M$ are at the distance greater than one. In this paper we consider the problem of finding maximum induced matchings in graphs of maximum degree three. The problem is NP-hard. We present an algorithm which finds the maximum induced matching of size at least $n/6+O(1)$, where $n$ is the number of vertices in a graph. Using this bound we achieve an approximation ratio of 1.8 in cubic graphs.
|websites: Arnold Beckmann||2008-05-23|