我试图使用贪婪方法解决二分图上的最大独立集问题.所以遇到了这篇文章,这正是我试图做的事情.但我只关注二分图.答案中的反案例不是二分图.是否有任何二分图表这个不适用？
Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G
S = union(S, {v})
remove v and its neighbors from G
return S