A note on the P-time algorithms for solving the maximum independent set problem
Navid Nasr Esfahani, Parisa Mazrooei, Kaveh Mahdaviani, Behnaz Omoomi · 2009
In this article, the problem of finding maximum (weight) independent set (M(W)IS) is investigated. It is known that this problem belongs to the class of NP-hard problems. Although, there are polynomial time (P-time) algorithms to solve the M(W)IS problem for some special classes of graphs. Here, we propose a general scheme which extends all of classes that the M(W)IS problem is solvable for them in P-time. This general scheme, based on any P-time algorithm for a class of graphs C, generates a new P-time algorithm to solve the M(W)IS problem for graphs in an extension of the class C. Moreover, this new algorithm is robust.