Алгебраический подход к FPT-алгоримам. Multilinear Detection

Speaker: 
Иван Михайлин
Date: 
Wednesday, February 19, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

Применение MD в FPT-алгоритмах для задач $k$-путь, $k$-дерево, $t$-доминантное множество, $k$-непересекающихся треугольников.

Рандомизированный алгоритм для MD.

Нижняя оценка на размер рабочего кольца в алгебраическом подходе к MD через сведение к коммуникационному протоколу на Set Disjointness. Оптимальности существующих алгоритмов.