Прошел семинар лаборатории: "Алгоритмы на графах малой древесной ширины", часть вторая

Прошел семинар лаборатории теоретической информатики 6 ноября 2025 года.

МЛ ТИ

Кауркин Владимир Владиславович,
Международная лаборатория теоретической информатики: стажер-исследователь

Доклад представляет собой продолжение лекции «Алгоритмы на графах малой древесной ширины», сделанной на семинаре международной лаборатории теоретической информатики 30.10.2025.

На предыдущем семинаре мы успели разобрать некоторые свойства путевой и древесной ширины; то, как можно строить параметризованные  алгоритмы на графах фиксированной древесной ширины, а также сформулировали теорему Курселя и посмотрели как можно выражать различные свойства на графах в MSO2. 

На этом докладе разобрали собственно доказательство теоремы Курселя, а также теорем на которые опирается доказательство (теорема Бьюхи и теорема Донера-Тэтчера-Райта). Обсудили FPT-алгоритм для приближенного вычисления древесной ширины.

Запись семинара будет представлена позже