Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Метод итеративного сжатия
Параметризованные алгоритмы


Что: Лекция
Когда: Среда, 30 сентября 2015, 18:00–19:30
Где: ПОМИ РАН

Описание

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

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

Видео