Прямой алгоритм проверки изоморфизма графов
Пролубников А.В.

Омский государственный университет, Омск, Россия

Аннотация:
Предлагается алгоритм решения задачи проверки изоморфизма графов. Алгоритм является прямым, в том смысле, что он не является модификацией схемы рекурсии с возвратом, на основе которой построены наиболее эффективные алгоритмы решения задачи. Решение задачи находится за число итераций алгоритма, не превышающее число вершин в графах. Показывается, что алгоритм является полиномиальным по числу используемых элементарных машинных операций и по используемой памяти. Исследуется класс графов, на котором алгоритм дает решение задачи.

Литература:

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982.
Hopcroft, Wong A linear time algorithm for isomorphism of planar graphs // Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 1974. - Р. 172-184.
Luks Isomorphism of graphs of bounded valence can be tested in polynomial time // Proceedings of the 21-st IEEE FOCS Symp., 1980. - 42, 49,
Hoffmann Group-Theoretic Algorithms and Graph Isomorphism // Lecture Notes in Computer Science 1982. -Chapter V. - P.127-138,
Babai L., Grigoryev D., Mount D. Isomorphism of graphs with bounded eigenvalue multiplicity // Proc. 14th ACM symp. On theory of comput, STOC, 1982. - Р. 310-324.
Цветкович Д. и др. Спектры графов. Теория и применение. - Киев: Наукова думка, 1984.
Faizullin R., A. Prolubnikov An algorithm of the spectral splitting for the double permutation cipher // Pattern recognition and image analysis. MAIK, Nauka. 2002. - Vol. 12. - No. 4. - Р. 365-375.
Годунов С.К. и др. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. - Новосибирск: Наука, 1988.
Гантмахер Ф.Р. Теория матриц. - М.: Наука, 1976.
Бахвалов Н.С. Численные методы. - М.: Наука, 1975. - Т.1.
Foggia P., Sansone C., Vento M. A Database of graphs for isomorphism and sub-graph isomorphism benchmarking // Proc. of the 3rd IAPR TC-15 international workshop on graph-based representations, Italy, 2001. - P.157-168.