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

Древесное разложение (tree decomposition) и древесная ширина (treewidth)
Параметризованные алгоритмы


Что: Лекция
Когда: Среда, 28 октября 2015, 18:00–19:30
Где: ПОМИ РАН

Описание

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

Видео