Laboratory of Mathematical Logic at PDMI

Пятница, 15 февраля, ауд. 203. Начало в 17:00.

Докладчик: Иван Близнец (Академический университет).

Тема: Алгоритм для поиска максимального хордального подграфа в данном графе за время быстрее, чем 2^n.

Abstract

Хордальными графами являются графы, не содержащие индуцированных подгафов циклов на 4 и более вершинах. В докладе будет представлен алгоритм поиска максимального индуцированного хордального графа в заданном графе G с временем работы , с<2. Доклад по совместной работе с Виллангером, Пилипчуком и Фоминым.