Блог пользователя MarioYC

Tree isomorphism
Автор MarioYC, 12 лет назад, По-английски
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 :)
  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
By the way here is a problem to give the algorithm a try :  http://www.spoj.pl/problems/TREEISO/
→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Use linear-time radix sort to sort node labels.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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 ((())(())).

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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!

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 7   Проголосовать: нравится +9 Проголосовать: не нравится

    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

    → Ответить