1 citations · 1 across the 2 of their papers we have counts for
2 papers
cs.DS2007★ 1 cited
A polynomial time -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…
cs.DS2007
On the approximability of the vertex cover and related problems
Qiaoming Han, Abraham P. Punnen
In this paper we show that the problem of identifying an edge in a graph such that there exists an optimal vertex cover of containing exactly one of the nodes $…