Isomorphism Testing of Rooted Trees in Linear Time

Anna Lindeberg

The AHU-algorithm solves the computationally difficult graph isomorphism problem for rooted trees, and does so with a linear time complexity. Although the AHU-algorithm has remaine…