Точные алгоритмы для задачи раскраски графа
Алгоритмы для NP-трудных задач


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

Описание

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

Видео

Приложенные файлы