A note on greedy algorithms for the maximum weighted independent set problem

摘要

In this paper, we consider three simple and natural greedy algorithms for the maximum weighted independent set problem. We show that two of them output an independent set of weight at least ∑_(v∈V(G))W(v)/[d(v)+1] and the third algorithm outputs an independent set of weight at least ∑_(v∈V(G))W(v)~2/[∑_(u∈N_G~(v))W(u)].