Find minimum vertex Cover for bipartite graph given the maximum matching

algorithm graph set matching bipartite
user1084113 picture user1084113 · Sep 16, 2012 · Viewed 14.1k times · Source

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

Answer

Luixo picture Luixo · Nov 1, 2015

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).

Related questions

Good Java graph algorithm library?

Has anyone had good experiences with any Java libraries for Graph algorithms. I've tried JGraph and found it ok, and there are a lot of different ones in google. Are there any that people are actually using successfully in production …

Read More
What is the maximum number of edges in a directed graph with n nodes?

What is the maximum number of edges in a directed graph with n nodes? Is there any upper bound?

Read More
How to trace the path in a Breadth-First Search?

How do you trace the path of a Breadth-First Search, such that in the following example: If searching for key 11, return the shortest list connecting 1 to 11. [1, 4, 7, 11]

Read More