2
$\begingroup$

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes that are adjacent (means that for all v in Z, his parent and his childs are not in Z). A subgroup weight defined as the sum of the numbers of the included nodes in it.

Find an algorithm that finds an Isolated subgroup with the maximum weight.

I've tried to solve this question by set the root as the first node in the subgroup, then skip on his children and get the grandchild nodes.. something like that, but I don't find any greedy algorithm which can always take the nodes with the maximum number in it. I thought about to sort the tree in a way that the left child of a node is minimum and the right child is maximum, but what if a node have more than 2 childs?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

Hint: Write a dynamic programming algorithm that solves the problem for a subtree in two cases, either where you take the root node or you don't. You should be able to come up with a recursive relationship between these cases for a parent node at the top of a tree and children nodes at the tops of their trees. Basically, either you take the root node at the parent and then you do not take the root node at any child, or you do not take the root node at the parent and then you take the root node at at least one child (but not necessarily all of them). Then dynamic programming solves the problem quickly.

$\endgroup$
1
  • $\begingroup$ thanks for the answer, both of the answers are the same and because of the i did +1 to both of you $\endgroup$
    – Elior
    May 14, 2014 at 10:44
1
$\begingroup$

This is very famous Maximum Independent Set problem in Graphs, in your case it's in a rooted tree. For a solution check this Lecture Note. The solution is not very tough and I think you can read it by yourself.

$\endgroup$
4
  • $\begingroup$ thanks for the answer, both of the answers are the same and because of the i did +1 to both of you $\endgroup$
    – Elior
    May 14, 2014 at 10:45
  • $\begingroup$ so the complexity time is depends on the length of the tree right? if it's the recursive solution it takes O(lgn) ? $\endgroup$
    – Elior
    May 14, 2014 at 10:48
  • $\begingroup$ What is length of a tree? Did you mean height? $\endgroup$ May 14, 2014 at 14:34
  • $\begingroup$ The complexity is proportional to the height or number of levels of a tree. Now, in worst case height of a tree is $O(n)$ and thus the complexity is $O(n)$, not $O(\log n)$ . $\endgroup$ May 14, 2014 at 14:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .