Что: | Лекция |
Когда: | Среда, 14 мая 2014, 18:00–19:30 |
Где: | ПОМИ РАН |
В докладе рассмотрим FPT алгоритм для задачи Feedback Vertex Set Problem в ориентированном графе. Для этого построим сведение к задаче поиска Skew Separator problem, для которой предоставим решение. Сложность алгоритма исходной задачи $ 4^kk!n^{O(1)} $.