SinByCos's blog

Need O(VE) Bipartite Matching code please
By SinByCos, history, 6 years ago, In English

I've learnt the O(VE) Bipartite Matching solution but I'm not sure what the algorithm is called and how it is implemented. It is the one similar to this here, that doesn't use flows, only finding and extending augmenting paths till there is none: http://www.columbia.edu/~cs2035/courses/ieor8100.F12/lec4.pdf Could anyone share code please?

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopcroft-Karp runs in O(E sqrt(V)).

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The paper basically describes how to set up a flow network so that you can use a max-flow algorithm. E.g. using Ford-Fulkerson or Edmonds-Karp gives you a O(VE) solution. Or use Dinic's algorithm on the network and you get a solution.

→ Reply