A polynomial time $\frac{3}{2}$ -approximation algorithm for the vertex cover problem on a class of graphs

Qiaoming Han, Abraham P. Punnen, Yinyu Ye

We develop a polynomial time 3/2-approximation algorithm to solve the vertex cover problem on a class of graphs satisfying a property called ``active edge hypothesis''. The algorit…