An optimized circuit simulation method for the isomorphism determination of regular graphs

In this paper, an optimized circuit simulation method is presented, based on the original circuit simulation method proposed in our former paper, to solve the problem of isomorphism determination of regular graphs. The original circuit simulation method has been proved to be able to solve the isomorphism determination problem of random graphs in polynomial time, to further apply the method in the isomorphism determination of regular graphs, some modification is needed, and in this paper, an idea of breaking vertex symmetry is introduced. Tests on regular graphs demonstrate that the optimized circuit simulation method can solve the problem of isomorphism determination of regular graphs in polynomial time.