CODEWITHSUNDEEP
algorithmmathgraph-theorydiscrete-mathematics
Ernesto Carvajal
Ernesto Carvajal

Reputation: 99

Selecting one vertex from each edge

This is a straightforward problem to explain and yet I'm having some tough time on figuring out a solution. My favorite kind!

Let G=(V,E) be a bipartite graph. I need to compute the minimum subset V' such that for every edge e=(u,v), u belong to V' OR v belong to V'. If there is more than one solution, anyone is acceptable.

|V| <= 2000

|E| <= 10000

Any hint could be useful :D

Upvotes: 1

Views: 80

Answers (1)

Per
Per

Reputation: 2624

Konig's theorem is relevant.

Upvotes: 2

Related Questions