7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Please restrict yourself to only one question per post. $\endgroup$ – Raphael Jun 10 '16 at 21:22
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 10 '16 at 21:22
  • 1
    $\begingroup$ Also, what have you tried? Where have you looked? $\endgroup$ – Raphael Jun 10 '16 at 21:23
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.