Laboratory of Mathematical Logic at PDMI

Пятница, 6 июня, комната 106. Начало в 16:00.

Докладчик: И. Н. Пономаренко.

Тема: Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время.

Abstract

Граф называется циркулянтным, если он изоморфен какому-либо графу Кэли над циклической группой. До настоящего времени не было известно алгоритмов полиномиальной сложности для распознавания циркулянтных графов (в классе всех графов) и для проверки их изоморфизма. В докладе описываются такие алгоритмы, найденные недавно докладчиком совместно с С.А.Евдокимовым.