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 Sigma(vis an element ofV(G)) W(v)/[d(v) + 1] and the third algorithm outputs an independent set of weight at least Sigma(vis an element ofV(G)) W(v)(2)/[Sigma(uis an element ofNG+(v)) W(u)]. These results are generalization of theorem of Caro and Wei. (C) 2002 Elsevier Science B.V. All rights reserved.