GRAPH ISOMORPHISM ALGORITHMS BASED ON TREES AND PATHS

Polynomially bounded algorithms are presented for testing isomorphism of two classes of graphs: the strongly regular graphs, which have been difficult for many previous isomorphism algorithms to process, and the compact graphs (graphs with diameter of 2 whose complements also have diameter of 2).; The strongly regular graphs algorithm is based on the use of a profiling technique to enumerate the positions of the vertices with respect to the shortest paths of length 2 and the neighborhoods of the vertices on the paths, thus providing a measure of the graph structure. As a consequence of the rigid constraints imposed (by definition of strongly regular graphs) on the interrelationships among the vertex neighborhoods, the path-based algorithm is shown to generate the automorphism partition for strongly regular graphs.; The compact graphs algorithm is based on enumeration of the breadth-first string trees of height at most 3 which can be embedded in each graph, and of the positions of each vertex within each tree. It is shown that equality of profiles based on these enumerations, the calculation of which is of polynomial complexity, constitutes a sufficient condition to prove isomorphism for the compact graphs. Since the strongly regular graphs are compact and can be tested by both algorithms, a discussion of their relative performance for this class is provided.; A general version of the tree-based algorithm is given in terms of a non-specific class of trees. A parallel version of this algorithm is discussed and analyzed.; The complexities (polynomial, isomorphism complete, etc.) of and algorithms for isomorphism testing for various graph classes, and selected other problems, are surveyed and discussed. The hierarchy of isomorphism problems of various complexities is extended to include the strongly regular and compact graphs. The position of the subgraph isomorphism problems on which the new isomorphism algorithms are based is established with respect to the general hierarchy of complexities.