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

Древесное разложение (продолжение)
Parameterized Algorithms

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

Description

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

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

Video