Accelarating graph isomorphism algorithm by finer classification of layered graphs

No polynomial time algorithm is known for the graph isomorphim problem. In this paper, we determine graph isomorphism by limiting the. range of I to I correspondences between two graphs as follows: We reconfigure the graphs into layered graphs. labeling vertices by partitioning the set of vertices by degrees. We prepare a correspondence table by means of whether labels on 2 layered graphs match or not. Using that table, we seek a I to I correspondence between the two graphs. By limiting the search for I to I correspondences between the two graphs to information in, the table, we are able to determine graph isomorphism more efficiently than by other known algorithm.. The algorithm was timed with on experimental data and we obtained a complextity of O(n(4)).