A graph isomorphism algorithm using pseudoinverses |
| |
| Authors: | J M Bennett J J Edwards |
| |
| Institution: | (1) Basser Department of Computer Science, University of Sydney, 2006, NSW, Australia;(2) School of Computing Sciences, University of Technology, PO Box 123, 2007 Sydney, Broadway, NSW, Australia |
| |
| Abstract: | For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn
2) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time. |
| |
| Keywords: | Graph isomorphism pseudoinverse |
| 本文献已被 SpringerLink 等数据库收录！ |
|
