Точные алгоритмы для задачи раскраски графа

3-раскраска: время O∗(2^n) и полиномиальная память с помощью перебора, улучшение до O∗(1.9^n); вероятностный O∗(1.5^n) алгоритм через сведение к задаче 2-выполнимости; O∗(^n) через использование максимальных по включению независимых множеств. Общая задача: время O∗(3^n) и память O∗(2^n) через динамическое программирование, улучшение до O∗(^n) через максимальные по включению независимые множества; время и память O∗(2^n) через формулу включений-исключений и быстрое преобразование Фурье. Лекция №8 в курсе “Алгоритмы для NP трудных задач“ (осень 2013). Преподаватель: Александр Куликов. Страница лекции на сайте CS центра: