Блог пользователя pain_is_salvation

Автор pain_is_salvation, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Its NP problem XD

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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