City:
Test
Saint Petersburg
Novosibirsk
Kazan
Language:
Русский
English
About CS Club
Courses
Lecturers
Schools
Login
Registration
Метод итеративного сжатия
Parameterized Algorithms
What:
Lecture
When:
Wednesday, 30 September 2015, 18:00–19:30
Where:
ПОМИ РАН
Description
Метод итеративного сжатия. Демонстрация метода на примере вершинного покрытия. Задачи:
Задача разрезание контуров в графах турнирах(Feedback Vertex Set in Tournaments) $2^k n^{O(1)}$.
Задача разрезание контуров в произвольных неориентированных графах $5^k n^{O(1)}$.
Video