test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
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
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