Design and Analysis of Algorithms20765 marksApproximation Algorithms
Explain the approximation for solving vertex cover with a suitable example.
Explain the approximation for solving vertex cover with a suitable example. [5]
A vertex cover of an undirected graph G = (V, E) is a subset V' ⊆ V such that for every edge (u, v) ∈ E, at least one of u or v belongs to V'. The optimization problem is to find the vertex cover with the fewest vertices. The approximation problem is to find a vertex cover with few vertices (not ...