2
$\begingroup$

(I've been stuck on this homework assignment for far too long)

I need to find the number of independent sets in a tree.

For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are children of A and D, E are children of B. This tree has 14 independent sets.

I assume that the algorithm will be recursive and I think that I should make each level of a tree into a linked list, so B->C and D->E, but more than that I'm stumped.

Would grealy appreciate help.

$\endgroup$
  • $\begingroup$ Consider constructing the tree step by step, starting with the trivial 1-node tree and repeatedly bringing in children of present vertices in an arbitrary order. Can you come up with a recursive formula for the number of independent sets at any given point in time? If so, transform this analysis into a dynamic programming solution. $\endgroup$ – Yonatan N Oct 3 '13 at 1:04
3
$\begingroup$

Hint: Compute recursively the number of independent sets (a) containing the root, (b) not containing the root.

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