I've a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints:
- The selected nodes must be the optimal solution (maximal sum of weight).
- If one node is flagged no adjacent nodes can be flagged.
- If a node is flagged it will be called: "directly controlled", the adjacent nodes instead will be called: "indirectly controlled", all nodes must be directly or indirectly controlled.
I think is a dynamic programming problem (a greedy approach didn't find always a optimal solution), the first two constraints are a typical maximum independent subset problems, but i cannot find a solution with the third constraint included. Any idea? Thanks