—The vertex canonical labeling technique is one ofthe powerful methods in solving the graph isomorphismproblem. However, some famous algorithms relied upon thistechnique are incomplete due to their non-zero probabilityof rejection. In this paper, we advance a new method ofvertex canonical labeling and propose a complete graphisomorphism algorithm with depth-first backtracking. Thetime complexity of this algorithm is O(n^α) where n^α isthe number of backtracking points and (h-1)/2≤α≤(h+1)/2for h=logn in most cases. Finally, the proposed algorithm iscompared with other researches on many types of graphs.The performance results validated that our algorithm isefficient for a wide variety of families of graphs.
展开▼
