Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Representative Sets For Multisets
event speaker icon
Ariel Gabizon (CS, Technion)
event date icon
Wednesday, 26.11.2014, 12:30
event location icon
Taub 401
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 Daniel Lokshtanov and Michal Pilipczuk