Tuesday, July 26, 2016

Finding minimum vertex cover size of a graph using binary search

Find the size of the minimum size vertex cover, that is, cardinality of a vertex cover with minimum cardinality, for an undirected connected graph with V vertices and m edges.
Examples:
Input: V = 6, E = 6
       6
             /
     /
    1 -----5
   /|\
  3 | \
  \ |  \
    2   4
Output: Minimum vertex cover size = 2
Consider subset of vertices {1, 2}, every edge 
in above graph is either incident on vertex 1 
or 2. Hence the minimum vertex cover = {1, 2}, 
the size of which is 2.

Input: V = 6, E = 7
     2 ---- 4 ---- 6
    /|      |
  1  |      |
    \|      |
     3 ---- 5
Output: Minimum vertex cover size = 3
Consider subset of vertices {2, 3, 4}, every
edge in above graph is either incident on 
vertex 2, 3 or 4. Hence the minimum size of
a vertex cover can be 3.
http://www.geeksforgeeks.org/finding-minimum-vertex-cover-graph-using-binary-search/

No comments:

Post a Comment