Computer Science Club

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

Semester	Branch
autumn 2010	Saint Petersburg

Graph Isomorphism Problem