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

Древесное разложение (tree decomposition) и древесная ширина (treewidth)
Parameterized Algorithms

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

Description

Определение древесного разложения (tree decomposition) и древесной ширины(treewidth). Определение хорошего древесного разложения (nice tree decomposition). Задача о максимальном независимом множестве параметризованная древесной шириной, алгоритм с временем работы \(2^{tw}\cdot O(n)\)

Video