My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below:
- How many isomorphism classes of trees with n vertices are there?
- What are the classical algorithms to decide if two given trees are isomorphic?
- Is there a nice (computable?) isomorphism invariant?
Of course, the answers may depend on the structure used to define the trees, but I guess the correct choice of structure is part of the answer I am seeking.
Asked By : Rodrigo A. Pérez
Answered By : Yuval Filmus
There is a classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman. The algorithm actually uses a simple isomorphism invariant. See for example lecture notes of Vikram Sharma. Using this, you can solve unrooted tree isomorphism in linear time, as described for example in Smal's slides. Another classic algorithm is due to Buss.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/59515
0 comments:
Post a Comment
Let us know your responses and feedback