Noon lecture
list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)
On 9.4.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 | 2018 | 2019 | 2020 | newer lectures)
Webmaster: kamweb.mff.cuni.cz Archive page