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

Cut-and-Count (Сергей Копелиович)
Seminar on parameterized algorithms

What: Lecture
When: Wednesday, 05 March 2014, 18:00–19:35
Where: ПОМИ РАН

Description

Краткое повторение определений, связанных с 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) \). Нижние оценки для описанных задач.