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

Правка en1, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский fakerman 2019-03-23 00:06:45 475 Initial revision (published)