1
$\begingroup$

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 ?

  • 0
    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?2012-06-17
  • 0
    Sorry i forgot about tag. Yes, i heard about dynamic programming.2012-06-17
  • 0
    Well then, I left you a hint, if you need some more help, just post comments to it and I will try to explain.2012-06-17
  • 0
    If we have a root in our tree, that we walk up and trying to find the best sum, aren't we ?2012-06-17
  • 0
    And what we can go with this tree? http://desmond.imageshack.us/Himg41/scaled.php?server=41&filename=20262900.png&res=landing2012-06-17
  • 0
    We go upper from node with 3 and sum 3+7 = 10. If it is bigger than root of this subtree we mark this sum and go to another subthree. Am I right?2012-06-17
  • 0
    And if we have got two root of smaller subtrees we must choose better solution -> sum of smaller trees or roots. Is it ok? Sorry for my english :)2012-06-17
  • 0
    Very close. Let $t[node]$ denote the solution for the subtree starting with $node$ if $node$ is taken, and $s[node]$ if it is not taken. Then $t[node] = v[node] + \sum_{c \text{ is a child of }node} s[c]$ and $s[node] = \sum_{c \text{ is a child of }node} \max(t[c],s[c])$.2012-06-17
  • 0
    Ok, thank you very much.2012-06-17

1 Answers 1

1

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