On 09.04.2009 at 12:20 in S6, there is the following noon lecture:
Computing Large Matchings Fast
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.
Modified: 19. 10. 2010