Abstract:

The two important methods of distinguishing undirected graph isomorphism,namely the canonical labeling algorithm and the vertex partition algorithm,both have their own disadvantages. Specifically,the former can not work for those graphs which cannot be canonically labeled,and,this latter has to backtrack and try again and again,which results in exponential time cost. For any two isomorphic undirected graphs,new supergraphs can be
constructed by adding a new vertex and its incident edges to each graph. The supergraphs are isomorphic if and only if ths neighbors of the new vertexes preserve the isomorphic relation in the original isomorphic graphs. Based on this necessary and sufficient condition,a candidate set of isomorphic functions is selected with the help of an efficient necessary condition. Then,by distinguishing the supergraph isomorphism according to the subgraph isomorphism,a fast algorithm without backtracking is proposed to reduce the time cost and guarantee the distinguishing results.Theoretical and experimental results on some real cases demonstrate that the proposed algorithm is effective.

Key words: undirected graph isomorphism, fast algorithm, canonical labeling algorithm, vertex partition algorithm