I'm trying to write an algorithm to compute a minimum size dominating set of an undirected graph G(V,E).

I think the following works: 1) Sort vertices by number of edges (descending) 2) Add the first vertex to the set D (which will be the dominating set output) 3) Delete all vertices connected to D by one edge 4) Add the next vertex and then repeat until you run out of vertices.

I was wondering what the running time of this would be?

  • $\begingroup$ You can run this algorithm in $O(nlgn)$. Hint: All you need is a smart way to do (3). $\endgroup$ – jjohn Oct 26 '15 at 10:35
  • 3
    $\begingroup$ Or $O(n+m)$. By the way, the algorithm won't give you a minimum size dominating set. $\endgroup$ – Pål GD Oct 26 '15 at 10:36
  • $\begingroup$ Yeah. There's a nice way to do sort in this instance! p.s I forgot the $m$ factor in complexity. It's actually $O(nlgn +m)$ but,yeah, @PålGD's solution is better $\endgroup$ – jjohn Oct 26 '15 at 10:39
  • $\begingroup$ Why won't it give me a minimum size dominating set? $\endgroup$ – Spaceman Oct 26 '15 at 11:25
  • 2
    $\begingroup$ Why would it give a minimum dominating set? The onus of proof is on you. $\endgroup$ – Yuval Filmus Oct 26 '15 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.