Write short notes on

  • Vertex cover problem
  • Strassen’s matrix multiplication
  • Approximation algorithm and its uses

 

Ans

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': {} };

Related Questions