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.