Computability in Europe 2008
Logic and Theory of Algorithms
Logic and Theory of Algorithms
Print this page
Regular Talk:
Induced matchings in graphs of maximum degree three
| 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
|