Noon lecture

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

On 18.05.2006 at 12:20 in S5, there is the following noon lecture:

A Simple $O (2^{0.288 n})$ Independent Set Algorithm

Dieter Kratsch

Abstract

We apply ``Measure and Conquer" to analyse a very simple Branch & Reduce algorithm solving the well-studied Maximum Independent Set problem. We obtain a running time of $O(2^{0.288 n})$, which is competitive with the current best time bounds obtained with far more complicated algorithms (and naive analysis). We also provide an $\Omega (2^{0.166 n})$ lower bound on the time complexity of the algorithm.

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