Что: | Лекция |
Когда: | Среда, 23 апреля 2014, 18:00–19:30 |
Где: | ПОМИ РАН |
В своем докладе я расскажу вероятностный с односторонней ошибкой \( 2^k\operatorname{poly}(n) \) алгоритм Бьорклунда для задачи нахождения \( k \)-цикла в неориентированном графе (т.е цикла, проходящего через \( k \) заданных вершин/рёбер), а также расскажу про другой результат Вальстрема для той же задачи.