rust-algorithms icon indicating copy to clipboard operation
rust-algorithms copied to clipboard

Add bipartite vertex cover alongside dinic

Open 0b01 opened this issue 5 years ago • 2 comments

Something like: https://github.com/mikolalysenko/bipartite-vertex-cover/blob/master/vcover.js

I can make a pull request when I'm done.

0b01 avatar Jan 13 '19 07:01 0b01

That would be sweet. I forget: is the vertex cover possible to construct from the output of Dinic/Hopcroft-Karp, or does it need a separate algorithm?

EbTech avatar Jan 14 '19 06:01 EbTech

I suppose the vertex set in question is K from https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)#Proof

Edit: Looks like the example you linked does something similar, I see.

EbTech avatar Jan 14 '19 06:01 EbTech