Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Induced matchings in graphs of maximum degree three


Speaker: Grazyna Zwozniak
Slot: Array, 17:10-17:30, col. 1

Abstract

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