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

Древесное разложение (продолжение)
Параметризованные алгоритмы

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

Описание

Задачи параметризованные древесной шириной:

  1. Доминирующее множество \(4^{tw} n^{O(1)}\).
  2. Дерево Штейнера \(2^{O(tw \log{tw})} n^{O(1)}\).

Видео