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

Введение (Александр Куликов)
Семинар по параметризованным алгоритмам


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

Описание

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

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

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