25872.5's blog

By 25872.5, history, 14 months ago, In English

Hello!! I have recently studied max flow algorithm and about bipartite matching.As bipartite graph is simpler compared to general graph,is there any way we could reduce the space and time complexity when we apply edmonds_karp to it?

Can we reduce the space complexity to O(N) instead of using usual adjacency matrix for residual graph representation which takes up O(N^2)?

Read more »

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