(24) * << * >> * Russian * English * Content * All Issues

On the computational efficiency of the spectral splitting algorithm for checking graph isomorphism

A.V. Prolubnikov1, R.T. Faizullin1
1 Omsk State University

 PDF, 272 kB

Pages: 136 - 143.

Abstract:
The article considers a heuristic algorithm for checking graph isomorphism. The algorithm is based on successive splitting of multiple eigenvalues of matrices associated with graphs: the matrices processed by the algorithm are the modifications of the graph adjacency matrices. The algorithm is based on successive perturbation of matrices and the solution of the corresponding systems of linear algebraic equations. The matrices are transformed into positive definite matrices, this allows to solve the systems of linear equations associated with them. The article proves computational efficiency of the algorithm in one of the fundamentally complicated situations for checking the graph isomorphism.

Keywords:
spectral splitting, graph isomorphism, heuristic algorithm, matrix, linear algebraic equation.

Citation:
Prolubnikov AV, Faizullin RT. On the computational efficiency of the spectral splitting algorithm for checking graph isomorphism. Computer Optics 2002; 24: 136-143.

References:
  1. Garey MR, Johnson DS. Computers and intractability: A guide to the theory of NP-completeness. New York: WH Freeman & Co; 1979.
  2. Tsvetkovich D, Dub M. Spectra of graphs. Theory and application [In Russian]. Kyiv: "Naukova Dumka" Publisher; 1984.
  3. Kikina AY, Faizullin RT. The algorithm for testing graph isomorphism [In Russian]. VINITI 21.06.95: 1789-B95.
  4. Hopcroft W. A linear time algorithm for isomorphism of planar graphs. Proc Sixth Annual ACM Symposium on Theory of Computing 1974: 172-184.
  5. Luks EM. Isomorphism of graphs of bounded valence can be tested in polynomial time. 21st Annual Symposium on Foundations of Computer Science 1980: 42-49.
  6. Hoffmann CM. Group-theoretic algorithms and graph isomorphism. Ch V. Berlin, Heidelberg: Springer-Verlag; 1982: 127-138.
  7. Bellman R. Introduction to matrix analysis. 2nd ed. Philadelphia: SIAM; 1997.
  8. Prolubnikov AV, Faizullin RT. Heuristic algorithm for solving of the graph isomorphism problem [In Russian]. Mathematical structures and modeling: Collection of scientific papers 2002; 9: 1-8.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20