todorokishotoua1's blog

By todorokishotoua1, history, 6 months ago, In English

So I came accross the following problem :

Given a rooted tree, find a minimum dominating set such that no two vertices in the dominating set share an edge and for all the vertices that is not in the set, there exists exactly one vertex in the set which is its neighbor. If such a set does not exists, report -1.

I know there is a dp solution for finding the minimum dominating set of a given tree, but i have no idea as to how to approach this question, especially since my dp on trees is really weak.

Any help as to how to approach the problem will be really appreciated. Thank you.

Dominating Set Definition

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it