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

Cut-and-Count (Сергей Копелиович)
Семинар по параметризованным алгоритмам


Что: Лекция
Когда: Среда, 05 марта 2014, 18:00–19:35
Где: ПОМИ РАН

Описание

Краткое повторение определений, связанных с treewidth (treewidth, nice tree). Сut & count — общий принцип. Дерево Штейнера (Shteiner Tree) на \( |V| = n \), \( |E| = m \) графе для множества \( T \). Решения для \( |T| = k \) за \( 3^k \cdot m \), использование cut & count, решение за \( 3^{tw} \cdot \operatorname{poly}(n) \). Покрытие ориентированными циклами (Directed Cycle Cover): решения за \( 3^n \) и \( 2^n \cdot \operatorname{poly}(n) \), использование cut & count, решение за \( 6^{tw} \cdot \operatorname{poly}(n) \). Нижние оценки для описанных задач.