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

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


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

Описание

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