On an algorithm of Zemlyachenko for subtree isomorphism

Zemlyachenko's linear time algorithm for free tree isomorphism is unique in that it also partitions the set of rooted subtrees of a given rooted tree into isomorphism equivalence classes. Unfortunately, his algorithm is very hard to follow. In this note, we use modern data structures to explain and implement Zemlyachenko's scheme. We give a full description of a free rendi tion of his method using some of his ideas and adding some new ones; in par ticular, the usage of the data structures is new. (C) 1999 Elsevier Science B.V. All rights reserved.