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