eidan's blog

Isomorphic Rooted Tree Problems
By eidan, history, 7 years ago, In English

I was reading about tree isomorphism and came across this paper. It explains an amazing algorithm developed by Aho, Hopcroft and Ullman which finds out if two rooted trees are isomorphic in linear time. I have searched for this problem on several online judges in order to test my implementation, but have had no success. If anyone has seen a problem that requires this algorithm could he/she be so kind to share the link?

Any help is appreciated :)

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Something like that? Problem

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

    Thank you for sharing. However, that is not exactly what I am looking for. That problem requires checking if two binary trees are isomorphic. I have actually already tested this algorithm on that problem XD. But now I want to test if my implementation works on any type of rooted tree, not only binary.

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

      I think it could help so Any type tree Problem

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

        That is a great example too. However, in that problem, the tree is not rooted.

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

          No, it doesn’t really matter. Can you see why?

          Spoiler
          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sorry for the possible necroposting, but there is a possible (but somewhat trivial) constant-optimization that can be done.

            If the numbers of centroids do not match, the trees are not isomorphic.

            If both have one centroid, it suffices to check after rooting by that centroid.

            If both have two centroids, then fix one centroid in one tree and check both centroids in the other tree.

            This gives a speed-up of about 2x in the worst-case :)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it -11 Vote: I do not like it

              Hey, If there are two centroids, then aren't they adjacent and rooting them at any would result in 2 isomorphic rooted trees. So isn't it meaningless to check for each when we can choose any from the first and same for the second tree?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                For example take $$$P_4$$$ and attach two vertices to one of the leaves. Centroids have different degrees so they can't result in two isomorphic rooted trees. We can get another example if we use $$$P_6$$$ instead of $$$P_4$$$. In this case rooted trees have different heights.

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

                  Hey, thank you for taking the time and helping me. I am sorry if this may sound dumb but can you please explain what $$${P_4}$$$ and $$${P_6}$$$ are.

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

                  $$$P_n$$$ stands for path of size $$$n$$$. check this (3 and 4 are centroids).

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

This appeared in the Indian online regional — https://www.codechef.com/problems/TWOTREES

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

763D

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

https://cses.fi/problemset/task/1700

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

https://community.topcoder.com/stat?c=problem_statement&pm=13841&rd=16500

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

Hey,

This one isn't rooted, but by using the technique ko_osaga mentioned above, it should be reducible into it anyway. It's from a recent ICPC Regional.

Hope it helps!

→ Reply