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

Статья представляет собой творческую компиляцию некоторых работ, посвященных проблеме изоморфизма графов и появившихся в последние годы.
В первой главе излагается подход к проблеме изоморфизма, сложившийся, главным образом, в работах Бабаи и Лакса. Этот, подход, представляющийся авторам обзора наиболее перспективным и результативным, имеет две характерные особенности: использование информации о специальном строении группы автоморфизмов и глубокое применение теории групп подстановок. В частности, приводятся доказательства распознаваемости изоморфизма графов с ограниченными валентностями за полиномиальное время и всех графов – за умеренно экспоненциальное время.
Во второй главе приведено вольное изложение результатов Филотти, Майера и Миллера об изоморфизме графов ограниченного рода. Приведены новые и более полные доказательства основных утверждений, а также алгоритм распознавания изоморфизма графов рода $g$ за время $O(v^{O(g)})$ где $v$ – число вершин.
В третьей главе обсуждаются некоторые распространенные приемы построения алгоритмов, распознающих изоморфизм, алгоритмы с вероятностными оценками, Лас Вегас-алгоритмы.
В четвертой главе рассматриваются связи проблемы изоморфизма графов с другими проблемами.