CODEWITHSUNDEEP
algorithmgraphsetmatchingbipartite
user1084113
user1084113

Reputation: 962

Find minimum vertex Cover for bipartite graph given the maximum matching

I seem to have found an algorithm but am having trouble understanding it, I was wondering if any of you knew the generic outline of the algorithm.

Here is the link to the algorithm I found on page 2

http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

Upvotes: 2

Views: 15228

Answers (2)

Luixo
Luixo

Reputation: 186

Algorithm is simple as that:

  1. Find unmatched vertex, mark it as not included in minimum vertex cover.
  2. Mark all matched neighbours of this vertex as included in minimum vertex cover.
  3. Treat all mates of vertexes from previous step as unmatched vertexes and repeat step 1.
  4. If recursion ended, repeat from step 1 (that is case of several connected components of graph).
  5. If there is no unmatched vertexes, take all remaining pairs and mark them any way you like (remember that one vertex in pair has to be included in minimum vertex cover, and other one has to be not included).

Upvotes: 13

iloahz
iloahz

Reputation: 4561

first you should know bipartite graph, two sets of vertexes, and edges, ok, you know that now.

then you need to choose some vertexes from the two sets, to cover all the edges. As long as one vertex is chosen, all the edges link to it is covered. Now your task is to choose the minimum number of vertexes, to cover all the edges.

the principle means, the minimum number you need equals to the number of max matching pairs.

Upvotes: -4

Related Questions