Изоморфизмы графов с простым спектром и древесные разложения по расстоянию

Abstract

Предложен полиномиальный алгоритм распознавания изоморфизма для графов, которые обладают цепным разложением, все компоненты которого имеют простой спектр. Алгоритм использует теоретико-групповые методы.

We give an algorithm solving Graph Isomorphism problem in polynomial time for graphs in which all pathwidth’s components have only simple eigenvalues. This algorithm is based on a group-theoretic approach.