Проблема изоморфизма графов

— Постановка. Задачи, эквивалентные проблеме изоморфизма графов. Изоморфно полные классы.
— Каноническая форма. Вероятностный алгоритм распознавания изоморфизма графов за полиномиальное время.
— Распознавание изоморфизма деревьев и планарных графов.
— Алгебраические леса и алгоритм Вейсфейлера-Лемана.
— Почти-полиномиальные алгоритмы распознавания изоморфизма графов и других комбинаторных структур.
— Алгоритмы для работы с группами перестановок (орбиты, принадлежность, порядок, стабилизаторы).
— Распознавание изоморфизма графов с ограниченными цветными классами. Неэффективность комбинаторных алгоритмов.
— Алгоритм Лакса для кубических графов. Графы ограниченной степени.
— Умеренно экспоненциальный алгоритм распознавания изоморфизма графов (Бабаи-Земляченко).
— Циркулянтные графы.

Страница курса на сайте Computer Science Club