The direct algorithm for checking graphs isomorphism
A.V. Prolubnikov

Omsk State University, Omsk, Russia

Full text of article: Russian language.

Abstract:
This paper presents an algorithm for solving the graphs isomorphism problem. The algorithm is direct in the sense that it is not a modification of the backtracking recursion scheme upon which the most efficient algorithms are built to solve the problem. The solution of the problem is out of the number of algorithm iterations not exceeding the number of nodes of graphs. It is shown that the algorithm is polynomial by the number of the used elementary computer operations and the used memory. The graph class where the algorithm provides solution to the problem is studied.

Key words:
graphs isomorphism problem, backtracking recursion scheme, nodes of graphs, polynomial algorithm.

Citation:
Prolubnikov AV. The direct algorithm for checking graphs isomorphism [In Russian]. Computer Optics 2007; 31(3): 86-92.

References:

  1. Garey M, Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness [In Russian]. Moscow: “Mir” Publisher, 1982.
  2. 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.
  3. Luks Isomorphism of graphs of bounded valence can be tested in polynomial time. Proceedings of the 21-st IEEE FOCS Symp. 1980; 42: 49.
  4. Hoffmann Group-Theoretic Algorithms and Graph Isomorphism. Lecture Notes in Computer Science 1982; V: 127-138.
  5. 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.
  6. Cvetkovic D, Doob M, Sachs H. Spectra of graphs. Theory and application [In Russian]. Kiev: Naukova Dumka, 1984.
  7. Faizullin R, Prolubnikov A. An algorithm of the spectral splitting for the double permutation cipher. Pattern recognition and image analysis 2002; 12(4): 365-375.
  8. Godunov SK, Antonov AG, Kirilyuk OP, Kostin VI. Guaranteed accuracy of solving linear systems in Euclidean spaces [In Russian]. Novosibirsk: “Nauka” Publisher, 1988.
  9. Gantmacher FR. The theory of matrices [In Russian]. Moscow: “Nauka” Publisher, 1976.
  10. Bakhvalov NS. Numerical methods [In Russian]. Moscow: “”Nauka” Publisher, 1975; 1.
  11. 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; 157-168.

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20