2
$\begingroup$

I am trying to figure out a greedy algorithm that finds the optimum (minimum) dominating set for any tree in linear time.

So a greedy algorithm to find a dominating set for a general graph is not optimum. It's an approximation of the optimum dominating set. But since this is a tree I am assuming that a greedy algorithm can give the optimum.

What i have so far is:

Select a vertex with the maximum number of adjacent vertices that are not dominated (that is, it's neighbors are either not dominated by one it its neighbors or they are not a dominated vertex themselves). We add this vertex to the dominated set.

We repeat this proceudue until all vertices are either in the dominated set or are neighbors of one of the dominated vertices.

But I am not sure this will give an optimum solution.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Take a look at at this for similar problem, and also for more than tree (also with explanation for tree): cs.uu.nl/docs/vakken/an/an-treewidth.ppt $\endgroup$
    – user742
    Dec 19, 2012 at 11:01

2 Answers 2

Reset to default
5
$\begingroup$

There is a simple dynamic programming algorithm. Root the tree at some arbitrary vertex. For each subtree, compute the optimal dominating set (a) with the root, (b) without the root.

Improve this answer
$\endgroup$
0
$\begingroup$

Choose the root so that it is a balanced tree. Put the parents of the leaves into the dominating set, do the same for the nodes of every other level.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.