Cut-and-Count

Докладчик: 
Сергей Копелиович
Дата: 
Wednesday, March 5, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

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