Some questions on tree isomorphism

Правка en2, от cote, 2020-06-03 12:00:39

In trying to solve the problem involving tree isomorphism, I came across a paper 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.

Теги isomorphism, #tree, ask a question

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский cote 2020-06-03 12:00:39 82
en1 Английский cote 2020-06-03 11:59:28 888 Initial revision (published)