City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Feedback Vertex Set Problem (Сергей Савинов)
Seminar on parameterized algorithms

What: Lecture
When: Wednesday, 14 May 2014, 18:00–19:30
Where: ПОМИ РАН

Description

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