8
$\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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Please restrict yourself to only one question per post. $\endgroup$
    – Raphael
    Commented Jun 10, 2016 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
    Commented Jun 10, 2016 at 21:22
  • 1
    $\begingroup$ Also, what have you tried? Where have you looked? $\endgroup$
    – Raphael
    Commented Jun 10, 2016 at 21:23

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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