Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



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

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

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

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

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



Введение в FPT-алгоритмы

Speaker: 
Александр Куликов
Date: 
Sunday, February 2, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

Определение параметризованной задачи и FPT-алгоритма. Сравнение функций $2^kn$ и $n^{k+1}$. Примеры FPT-задач: вершинное покрытие размера $k$, $k$-путь, $k$ непересекающихся треугольников. Примеры трудных задач: клика, независимое множество, доминирующее множество.

Ядра (кернелизация). Эквивалентность существования FPT-алгоритма и существования ядра. Простейшие примеры ядер: ядро размера $k(k+1)$ для вершинного покрытия, ядро размера $k^2$ для покрытия точек прямыми.

Примеры FPT-алгоритмов. Color coding и $k$-путь. Итеративное сжатие и задача об удалении нечётных циклов.


Pages