Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 09.04.2009 at 12:20 in S6, there is the following noon lecture:

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.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010