Suggest a Book

# Vertex cover using DFS

Level: unknown

posted Jun 17 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

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.

delete retag edit

## Stats

Posted: Jun 17 '12

Seen: 163 times

Last updated: Jun 17 '12