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

Метод динамического программирования (время: O(2^n), память: O(2^n)). Метод включений-исключений (время: O(2^n), память: O(1)). Матрица Татта и перманент, решение для двудольного графа за O(2^n/2) времени и O(1) памяти. Лекция №3 в курсе “Алгоритмы для NP-трудных задач“ (осень 2013). Преподаватель: Александр Куликов. Страница лекции на сайте CS центра: