CODEWITHSUNDEEP
algorithmgraphtime-complexitygreedyindependent-set
高翔宇
高翔宇

Reputation: 11

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

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

Upvotes: 1

Views: 330

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

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

Upvotes: 0

Related Questions