Vertex cover problem:
A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph. strong>Given an undirected graph, the vertex cover problem is to find minimum size vertex cover. It is a known NP Complete problem, i.e., there is no polynomial time solution for this unless P = NP. There are approximate polynomial time algorithms to solve the problem though. Following is a simple approximate algorithm.
Approximation algorithm for vertex cover
{
C=null
While E!=null
{
Pick any edge (uv)€E
C=CU{u,v}
Delete all edges incident to either u and v
}
Return C as approximate vertex cover.
}
atOptions = {
'key': 'a900f2dbf175e78754c26c6231a4b673',
'format': 'iframe',
'height': 90,
'width': 728,
'params': {}
};