Задача поиска кратчайшего цикла в графе через выбранные вершины

Задача поиска кратчайшего цикла в графе через выбранные вершины

Date:

Wednesday, April 23, 2014 - 18:00

Abstract:

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