[Solved]: Number of Independent Sets in a tree

Problem Detail: 

(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.

Asked By : Edgar Aroutiounian

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14768

 Ask a Question

 Download Related Notes/Documents