algorithm - 贪心算法的时间复杂度找到一个图的最大独立集

Question

一个简单的贪心算法来找到一个最大的独立集，我认为这将花费 O(n) 时间，因为不会访问超过两次的顶点。为什么wiki说需要O（m）时间？

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

标签： algorithmgraphtime-complexitygreedyindependent-set

Answer 1

如果您在 K _n/2,n/2上运行它，则未选择一侧的邻居每个都被标记为非 IS n/2 次。