Город:
Тест
Санкт-Петербург
Новосибирск
Казань
Язык:
Русский
English
О клубе
Расписание
Курсы
Преподаватели
Международные школы
Войти
Регистрация
Метод итеративного сжатия
Параметризованные алгоритмы
Что:
Лекция
Когда:
Среда, 30 сентября 2015, 18:00–19:30
Где:
ПОМИ РАН
Описание
Метод итеративного сжатия. Демонстрация метода на примере вершинного покрытия. Задачи:
Задача разрезание контуров в графах турнирах(Feedback Vertex Set in Tournaments) \(2^k n^{O(1)}\).
Задача разрезание контуров в произвольных неориентированных графах \(5^k n^{O(1)}\).
Видео