Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Induced matchings in graphs of maximum degree three

Edit abstract data

Speaker: Grazyna Zwozniak
Slot: Wed, 17:10-17:30, Room 20 (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 Valid HTML 4.01! Valid CSS!