On 13.03.2014 at 12:20 in S6, there is the following noon lecture:
Representative sets for multisets
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
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010