3

I am often faced with the problem of checking some property of trees (the graph ones) of a given size by brute force. Do you have any nice tricks for doing this? Ideally, I'd like to examine each isomorphism class only once (but after all, speed is all that matters).

Bit twiddling tricks are most welcome since n is usually less than 32 :)

I'm asking for slightly more refined algorithms than the likes of "loop through all (n-1)-edge subsets and check if they form a tree" for trees on n nodes.

2
  • 1
    What kind of tree ? What algorithm are you using currently to "walk" through the tree ? What isomorphism are you talking about ? The question is very vague Feb 13, 2011 at 18:32
  • 2
    General trees, that is, connected graphs with n nodes and n-1 edges. By isomorphism I mean en.wikipedia.org/wiki/graph_isomorphism. I'm not walking through a specific tree - I want to generate a list of all trees.
    – Erik
    Feb 13, 2011 at 18:52

2 Answers 2

3

This is in Knuth's The Art of Computer Programming volume on Combinatorial Algorithms. If I remember correctly, it's an exercise there. Since he has the solutions for such, I point you there.

1
0

Some googling turned up the following algorithm description: http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf. They adapt an algorithm for enumerating rooted trees to enumerating unrooted trees.

Apparently others have proved that this requires only amortised constant time per tree, and the PDF shows some performance measurements demonstrating this.

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.