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

Алгебраический подход к FPT-алгоримам. Multilinear Detection (Иван Михайлин)
Seminar on parameterized algorithms

What: Lecture
When: Wednesday, 19 February 2014, 18:00–19:35
Where: ПОМИ РАН

Description

Применение MD в FPT-алгоритмах для задач $ k $-путь, $ k $-дерево, $ t $-доминантное множество, $ k $-непересекающихся треугольников. Рандомизированный алгоритм для MD. Нижняя оценка на размер рабочего кольца в алгебраическом подходе к MD через сведение к коммуникационному протоколу на Set Disjointness. Оптимальности существующих алгоритмов.