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

Задача поиска кратчайшего цикла в графе через выбранные вершины (Р. Демидов)
Seminar on parameterized algorithms

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

Description

В своем докладе я расскажу вероятностный с односторонней ошибкой \( 2^k\operatorname{poly}(n) \) алгоритм Бьорклунда для задачи нахождения \( k \)-цикла в неориентированном графе (т.е цикла, проходящего через \( k \) заданных вершин/рёбер), а также расскажу про другой результат Вальстрема для той же задачи.