Что: | Лекция |
Когда: | Среда, 28 октября 2015, 18:00–19:30 |
Где: | ПОМИ РАН |
Определение древесного разложения (tree decomposition) и древесной ширины(treewidth). Определение хорошего древесного разложения (nice tree decomposition). Задача о максимальном независимом множестве параметризованная древесной шириной, алгоритм с временем работы \(2^{tw}\cdot O(n)\)