Пятница, 15 февраля, ауд. 203. Начало в 17:00.
Докладчик: Иван Близнец (Академический университет).
Тема: Алгоритм для поиска максимального хордального подграфа в данном графе за время быстрее, чем 2^n.
Abstract
Хордальными графами являются графы, не содержащие индуцированных подгафов циклов на 4 и более вершинах. В докладе будет представлен алгоритм поиска максимального индуцированного хордального графа в заданном графе G с временем работы
![$ c^n $](/sites/default/files/tex/1230947f43b27aa9d88ce40dd612f0fc301f8e01.png)
, с<2. Доклад по совместной работе с Виллангером, Пилипчуком и Фоминым.