A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
Douglas C. Schmidt, Larry E. Druffel · Journal of the ACM · 1976
A backtracking algorithm for testing a pair of digraphs for isomorphism is presented. The information contained in the distance matrix representation of a graph is used to establish an initial partition of the graph's vertices. This distance matrix information is then applied in a backtracking procedure to reduce the search tree of possible mappings. While the algorithm is not guaranteed to run in polynomial time, it performs efficiently for a large class of graphs.