Consider the following algorithm for Vertex Cover of a graph $G$ :
Run depth first search (DFS) on $G$.
Output the vertices which are not leaves in the DFS tree.
Prove the following :
The output is indeed a vertex cover.
This algorithm gives a 2-approximation for the minimum vertex cover.
Posted: Jun 17 '12
Seen: 163 times
Last updated: Jun 17 '12
