Some questions on tree isomorphism
Difference between en1 and en2, changed 82 character(s)
In trying to solve the problem [Binary Isomorphism](https://csacademy.com/contest/archive/task/binary-isomorphism/statement/)involving tree isomorphism, I came across a [paper](https://logic.pdmi.ras.ru/~smal/files/smal_jass08.pdf) explaining an algorithm for checking if two trees are isomorphic. ↵

However, I cannot understand the complexity analysis of the AHU algorithm described in the paper. Why is the worst case `O(N^2)`. It seems to me that when we go down in the tree the lengths of all the string we need to sort is decreasing as well, and hence we are dealing with something `O(NlogN)`. ↵

My second question is about the improvement part (section 4.3 AHU algorithm improvement). I don't understand what the author means by sorting by level, and how can we convert those strings (canonical names) to integers. ↵

Hope that someone could help me. Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English cote 2020-06-03 12:00:39 82
en1 English cote 2020-06-03 11:59:28 888 Initial revision (published)