A BULT Algorithm for Tree Isomorphism
Liang Hua-jin · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2005
Solving the tree isomorphism problem is equivalent to solve two problems: whether there exists a bi-jection between two graphs and whether the bi-jection maps on distinguished node in one graph to one distinguished node in the other graph.Based on the relation between graphs and trees,a bottom up layer traversing algorithm,BULT algorithm for short,with linear time complexity and space complexity to solve these two problems is given.And the correctness of the altgorithm is also proven in the paper.The result can be easily extended to graphs.