Точные алгоритмы для задачи о максимальном разрезе и задачи максимальной 2-выполнимости
Алгоритмы для NP-трудных задач


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

Описание

Точные алгоритмы со временем работы \( O^*(2^{\omega n/3}) \) и памятью \( O^*(2^{2n/3}) \). [Ryan Williams. Algorithms and Resource Requirements for Fundamental Problems. PhD thesis, 2007. PDF] [W03] [FK13]

Видео