| Что: | Лекция |
| Когда: | Воскресенье, 25 октября 2009, 11:40–13:10 |
| Где: | ПОМИ РАН |
| Слайды: | np_algorithms_lecture_251009.pdf |
$ 1.5^n $ алгоритм для задачи о 3-раскрашиваемости графа. $ \log(2n) $-приближенный алгоритм для задачи о минимальном множестве представителей. FPT-алгоритм для задачи о пути длины $ k $. $ 2^{2n/3} $ алгоритм для 3-SAT.
