我试图用贪婪的方法解决二分图上的最大独立集问题。所以遇到这个职位,这正是我想要做的。但我只专注于二部图。答案中的反案例不是双方图。有没有任何二分图,这一个不会工作?最大独立集合的二分图
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
Why is greedy algorithm not finding maximum independent set of a graph?
请在这里引用算法。有趣的问题,虽然。 – 2013-04-08 07:17:05
编辑!谢谢 – vinothkr 2013-04-08 07:20:10