Noon lecture

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

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

Representative sets for multisets

Ariel Gabizon

Abstract

The notion of a q-representative set for a family of subsets, originally arising in the Two-Families Theorem of Bollobás, has recently proven to be very useful in the design of parameterized and exact algorithms.

In this talk I will explain this notion. Then, to illustrate its usefulness, I will show how it was used by Fomin, Lokshtanov and Saurabh to design a fast algorithm for finding long simple paths in a directed graph.

Finally, I will describe a recent work where we generalize the notion of a representative set to a family of multisets and derive algorithmic applications.

Based on joint work with Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh

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