Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
1  
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 –  user742 Dec 19 '12 at 11:01
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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