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?NG+(v)W(u)]. These results are generalization of theorem of Caro and Wei.
greedy algorithms maximum weighted independent set carowei theorem