# Running time for algorithm to compute the minimum size dominating set

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?

• You can run this algorithm in $O(nlgn)$. Hint: All you need is a smart way to do (3). – jjohn Oct 26 '15 at 10:35
• Or $O(n+m)$. By the way, the algorithm won't give you a minimum size dominating set. – Pål GD Oct 26 '15 at 10:36
• 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 – jjohn Oct 26 '15 at 10:39
• Why won't it give me a minimum size dominating set? – Spaceman Oct 26 '15 at 11:25
• Why would it give a minimum dominating set? The onus of proof is on you. – Yuval Filmus Oct 26 '15 at 11:33