Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле
Алгоритмы для NP-трудных задач


Что: Лекция
Когда: Воскресенье, 22 сентября 2013, 13:00–14:35
Где: ПОМИ РАН

Описание

Метод динамического программирования (время: \( O^*(2^n) \), память: \( O^*(2^n) \)). [DPV06, глава 6]

Метод включений-исключений (время: \( O^*(2^n) \), память: \( O^*(1) \)). [FK10, глава 4]

Матрица Татта и перманент, решение для двудольного графа за \( O^*(2^{n/2}) \) времени и \( O^*(1) \) памяти. [Andreas Bjorklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010. [official], [PDF]], [Beating A Forty Year Old Result: Hamilton Cycles] [FK13]

Видео