Computing Large Matchings Fast

Ignaz Rutter

Universität Karlsruhe

Abstract

For some graph classes lower bounds for the size of a maximum matching are known. For example every 3-regular graph has a matching of size at least (4n-1)/9. In this talk we consider the question whether a matching of this size (which is known to exist) can be computed faster than computing a maximum matching.