Time complexity of greedy algorithm to find a maximal independent set of a graph

Question

A simple greedy algorithm to find a maximal independent set, I think it will take O(n) time since no vertex will be visited more than twice. Why wiki said it would take O(m) time?

Greedy(G)
while G is not empty (visited V in an arbitrary order)
    mark v as IS and v's neighbors as Non-IS
return all IS vertices

Sorry, this is the web link https://en.wikipedia.org/wiki/Maximal_independent_set, see the sequential algorithm. — 高翔宇, Jul 28 '20 at 09:21
m denotes the number of edges and n denotes the number of vertices. — 高翔宇, Jul 28 '20 at 09:22

score 0 · Answer 1 · answered Jul 28 '20 at 10:58

0

If you run it on K_n/2,n/2, the neighbors on the side not chosen each get marked as non-IS n/2 times.

answered Jul 28 '20 at 10:58

David Eisenstat

64,237
7
60
120

Time complexity of greedy algorithm to find a maximal independent set of a graph

1 Answers1