[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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14768  Ask a Question  Download Related Notes/Documents