fakerman's blog

By fakerman, history, 6 years ago, In English

I read somewhere that the complexity of maximum bipartite matching using Dinic's is the same as that of Hopcroft Karp. But the complexity of Dinic's is $$$O(V^2E)$$$, and creating the flow network to solve maximum bipartite matching via it will also result in a $$$O(V^2E)$$$ complexity. But Hopcroft Karp takes $$$O(E\sqrt{V})$$$ time, which is clearly better than Dinic's. Please help me clear this doubt.

Full text and comments »

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