Семинар МЛ ТИ "Алгоритмы на графах малой древесной ширины, часть вторая"
Первая часть семинара была озвучена на семинаре 30 октября 2025 года «Алгоритмы на графах малой древесной ширины»
Международная лаборатория теоретической информатики: стажер-исследователь
Аннотация: Доклад представляет собой продолжение лекции «Алгоритмы на графах малой древесной ширины», сделанной на семинаре международной лаборатории теоретической информатики 30.10.2025.
На предыдущем семинаре мы успели разобрать некоторые свойства путевой и древесной ширины; то, как можно строить параметризованные алгоритмы на графах фиксированной древесной ширины, а также сформулировали теорему Курселя и посмотрели как можно выражать различные свойства на графах в MSO2.
На этом докладе мы разберем собственно доказательство теоремы Курселя, а также теорем на которые опирается доказательство (теорема Бьюхи и теорема Донера-Тэтчера-Райта). Обсудим FPT-алгоритм для приближенного вычисления древесной ширины.
Первая часть доклада доступна по ссылке
Приглашаем всех заинтересованных!
Место проведения:
Очно - АУК Покровский бульвар 11, S224
Онлайн: Zoom