City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Parameterized Algorithms using Matroids
Saint Petersburg / autumn 2014, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Recently matroids have played important role in designing parameterized algorithms. During this series of lectures we will see a basic introduction to matroids and its applications in designing faster parameterized algorithms. Central tool in these developments is called "representative families''. We will try to understand this tool via several examples.

Date and time Class|Name Venue|short Materials
21 September
11:15–12:50
Matroid basics and its use as data structure, Lecture ПОМИ РАН video
21 September
13:00–14:35
Representative sets, Lecture ПОМИ РАН video
21 September
15:35–17:10
Vertex cover, Lecture ПОМИ РАН video