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