Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add bipartite vertex cover alongside dinic #8

Open
0b01 opened this issue Jan 13, 2019 · 2 comments
Open

Add bipartite vertex cover alongside dinic #8

0b01 opened this issue Jan 13, 2019 · 2 comments

Comments

@0b01
Copy link

0b01 commented Jan 13, 2019

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

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

@EbTech
Copy link
Owner

EbTech commented Jan 14, 2019

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
Copy link
Owner

EbTech commented Jan 14, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants