Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got one very hard problem.

Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes. Algorithm should run in poly time.

Can you help me to solve it ?

share|improve this question
    
1. Does this question has some context (i.e. is it a homework maybe, it does sound like one)? 2. Have you heard of dynamic programming? –  dtldarek Jun 17 '12 at 18:48
    
Sorry i forgot about tag. Yes, i heard about dynamic programming. –  user33884 Jun 17 '12 at 18:58
    
Well then, I left you a hint, if you need some more help, just post comments to it and I will try to explain. –  dtldarek Jun 17 '12 at 19:00
    
If we have a root in our tree, that we walk up and trying to find the best sum, aren't we ? –  user33884 Jun 17 '12 at 19:03
    
And what we can go with this tree? desmond.imageshack.us/Himg41/… –  user33884 Jun 17 '12 at 19:19
show 4 more comments

1 Answer

up vote 1 down vote accepted

Hint:

Root the tree in an arbitrary vertex and going bottom-up consider the best solution for every subtree if the top node of it is taken (and therefore none of the children are) or when it is not taken (so for any child you can, but don't have to take it).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.