Блог пользователя fakerman

Автор fakerman, история, 5 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится