Алгоритмы для NP-трудных задач (2013). Лекция 8

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

3-раскраска: время O∗(2n) и полиномиальная память с помощью перебора, улучшение до O∗(1.9n); вероятностный O∗(1.5n) алгоритм через сведение к задаче 2-выполнимости; O∗(1.45n) через использование максимальных по включению независимых множеств. Общая задача: время O∗(3n)  и память O∗(2n) через динамическое программирование, улучшение до O∗(2.45n) через максимальные по включению независимые множества; время и память O∗(2n) через формулу включений-исключений и быстрое преобразование Фурье.

Страница лекции на сайте Computer Science Club