MarioYC's blog

Tree isomorphism
By MarioYC, 13 years ago, In English
Hi everyone, today I was reading this paper to understand how to solve the tree isomorphism problem. However, it isn't explained how to make the final optimization from O(nlgn) to O(n), could someone explain the idea or provide a reference to it?

Thanks :)
  • Vote: I like it
  • +31
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it
By the way here is a problem to give the algorithm a try :  http://www.spoj.pl/problems/TREEISO/
→ Reply
»
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Today I found another problem about tree isomorphism from NWERC, here is the link.

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use linear-time radix sort to sort node labels.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

What if you just pick random ints a, b and make hash(leaf)=a and head(trees) = b*sum(map(hash,trees))? I think that would work fine, and it doesn't require sorting.`

Edit: Just found a counter example ((()())) vs ((())(())).

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain to me the following statement from the paper "The idea 2. Assign canonical names level and if canonical level names agree than replace canonical names with integers". How to replace canonical names with integers? Thanks!

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 7   Vote: I like it +9 Vote: I do not like it

    I know this blog is very old. However I have recently studied tree isomorphism and came across this blog and saw your question is unanswered. In a certain level all children of the vertices in this level are assigned a certain integer that represents a canonical name. If two children have a same integer value, it means the subtrees rooted in those children are isomorphic, as the canonical names that this integer represents are the same. Now for each vertex in the current level, we create a list of all the integers of the child labels of this vertex. We sort this list. Now we create a list of all lists in the current level and we sort this list too. If the lists of tree 1 and tree 2 mismatch, the trees are not isomorph and we can terminate. Otherwise we start mapping lists of the vertices in current level to label ID's.

    labelID = 0
For each list in level:
   If (current list != previous list) 
      labelID++
   ID[vertex corresponding with current list] = labelID
End For

    When level 0 has been processed and there has not been a mismatch, the trees are isomorphic. This algorithm is O(N log N). In order to reach O(N), we have to get rid of ordinary sorting. However I have not yet accomplished this.

    Corresponding code (https://www.spoj.com/problems/TREEISO/): https://ideone.com/Qyvo1W

    → Reply