City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Метод расщепления
Parameterized Algorithms

What: Lecture
When: Wednesday, 16 September 2015, 18:00–19:30
Where: ПОМИ РАН

Description

Метод расщепления (Bounded Search Trees, DPLL-algorithms). Вершинное покрытие \(1.47^k\) (Vertex Cover). Задача о разрезании контуров \((3k)^k \cdot poly(n)\) (Feedback Vertex Set). Ближайшая строка \(O^*((d+1)^d)\) (Closest String).

Video