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.