Title: Accelerations for Graph Isomorphism,
Abstract: In this paper, we present two main results. First, by only one conjecture
(Conjecture 2.9) for recognizing a vertex symmetric graph, which is the hardest
task for our problem, we construct an algorithm for finding an isomorphism
between two graphs in polynomial time $ O(n^{3}) $. Second, without that
conjecture, we prove the algorithm to be of quasi-polynomial time $
O(n^{1.5\log n}) $. The conjectures in this paper are correct for all graphs of
size no larger than $ 5 $ and all graphs we have encountered. At least the
conjecture for determining if a graph is vertex symmetric is quite true
intuitively. We are not able to prove them by hand, so we have planned to find
possible counterexamples by a computer. We also introduce new concepts like
collapse pattern and collapse tomography, which play important roles in our
algorithms.