= Brendan McKay
{c}
{tag=Computer science author}
= Brendan D. McKay
{c}
{synonym}
\b[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>.<Brendan McKay homepage at Australian National University>[Biographical heading and Software]{ref}
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, giving
$$
|\operatorname{Aut}(C_4)|=4\cdot2=8.
$$
These 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.<Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno>[Introduction, refinement-individualization framework and program comparisons]{ref}
Back to article page
