A Polynomial Time Algorithm for Undirected Graph Isomorphism.

Graph isomorphism is an important problem in graph theory. So far no polynomial time algorithms have been found for undirected graph isomorphism. A popular class of testing methods use necessary conditions to identify two non-isomorphic graphs. Unfortunately, there often exist some non-isomorphic graphs that satisfy these necessary conditions. Based on a necessary condition we proposed previously, this paper develops an O(n⁴) algorithm for undirected graph isomorphism using vertex partition and refinement. Also, our algorithm takes advantage of a recursive property that isomorphism of supergraphs will result in the isomorphism of subgraphs. Finally, the experiments on the Graph Database validated the correctness of this algorithm for graph isomorphism. [ABSTRACT FROM AUTHOR]