A Partition Method for Graph Isomorphism

AbstractComplexity of the graph isomorphism algorithms mainly depends on matching time which is directly related to efficiency of their partition methods. This paper proposed a partition method by sorted sequences of length-L path numbers, and divided cells of partition into 3 categories: not similar; completely similar; similar but not completely. The method was tested on several types of graphs with different order, each type with the same order 100 graphs. The results indicate that not similar cells can be refined by adding path length to other types or trivial cells if the vertex is not similar with all other vertices. For almost all asymmetric graphs, the path length is a small value, e.g., for 6-regular graphs with 100∼1000 vertices the average path length is 4 to get all cells to trivial ones