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

Метод итеративного сжатия
Parameterized Algorithms

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

Description

Метод итеративного сжатия. Демонстрация метода на примере вершинного покрытия. Задачи:

  1. Задача разрезание контуров в графах турнирах(Feedback Vertex Set in Tournaments) $2^k n^{O(1)}$.
  2. Задача разрезание контуров в произвольных неориентированных графах $5^k n^{O(1)}$.

Video