Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Doubt regarding complexity of bipartite matching using Dinic's and Hopcroft Karp

Revision en1, by fakerman, 2019-03-23 00:06:45

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English fakerman 2019-03-23 00:06:45 475 Initial revision (published)