Brendan McKay is a researcher in computational graph theory and an emeritus professor at the Australian National University. His institutional homepage identifies nauty as software for graph isomorphism and graph automorphisms.[ref]
Brendan McKay homepage at Australian National University. Biographical heading and Software
A graph automorphism is a relabeling that preserves adjacency within a graph. For an original cycle on four vertices, choose the image of one vertex in4 ways and then choose which of its two neighbors receives the next vertex in2 ways. The remaining images are forced, givingThese relabelings form a group. Computing such symmetries can avoid repeating equivalent branches of a structural search.
Graph canonical labeling addresses a complementary problem: assign a representative encoding so that isomorphic graphs receive the same canonical result. This makes it possible to compare structures whose input vertex names differ or to remove duplicate generated graphs. McKay's work on nauty made these tasks practical for many graph classes.
With Adolfo Piperno, he described the mathematical basis of individualization-refinement graph search and the implementations in nauty and Traces graph isomorphism software. Their paper connects the validity of the search framework with performance comparisons, while distinguishing the practical algorithms from a general worst-case efficiency claim.[ref]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Introduction, refinement-individualization framework and program comparisons
New to topics? Read the docs here!