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

Feedback Vertex Set Problem (Сергей Савинов)
Семинар по параметризованным алгоритмам


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

Описание

В докладе рассмотрим FPT алгоритм для задачи Feedback Vertex Set Problem в ориентированном графе. Для этого построим сведение к задаче поиска Skew Separator problem, для которой предоставим решение. Сложность алгоритма исходной задачи \( 4^kk!n^{O(1)} \).