Department of Applied Mathematics & Physics, Kyoto Univiversity
Technical Report #98009 (April, 1998)
An approximation of the minimum vertex cover in a graph
by Hiroshi Nagamochi and Toshihide Ibaraki
For a given undirected graph $G$ with $n$ vertices and $m$ edges,
we present an approximation algorithm for the minimum vertex cover problem.
Our algorithm finds a vertex cover within $2-\frac{8m}{13n^2+8m}$
of the optimal size in $O(nm)$ time.