pain_is_salvation's blog

Minimum Vertex Cover
By pain_is_salvation, history, 4 years ago, In English

Can anyone please provide a good tutorial on how to find the Minimum Vetex Cover of a graph ? P.S- Please don't provide geeks for geeks links.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Its NP problem XD

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Minimum Vertex Cover is an NP-hard problem. I assume you meant how to find Minimum Vertex Cover on a bipartite graph? In this case, you can use any Max flow algorithm to solve it (I will leave the flow graph modelling as an exercise for you).

→ Reply