Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Алгебраический подход к FPT-алгоримам. Multilinear Detection (Иван Михайлин)
Семинар по параметризованным алгоритмам


Что: Лекция
Когда: Среда, 19 февраля 2014, 18:00–19:35
Где: ПОМИ РАН

Описание

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