Which maximum flow algorithm is this?

Revision en2, by akash_goel, 2015-07-21 22:33:19

I read Cormen and Wikipedia pages for Max flow algorithms, but I feel that I'm very confused right now.

In my understanding, a max flow would basically work as follows:

  1. Find an augmenting path and maintain a parent array. Should be O(E) using BFS.
  2. Update the flow on all the edges on this path using the parent array. O(V) worst case. Update the max flow value.
  3. Repeat the above steps until no more augmenting paths are found and return the max flow.

My questions are:

Ql. What is the limit on the number of times step 1 (bfs) is required?

Q2. Is this Edmond Karp or Dinitz algorithm that I'm talking about?

This is my first post, so I hope you will point out any problems in the way I've framed this question. Thanks.

Tags max-flow, graph-theory, dinitz, edmond-karp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English akash_goel 2015-07-21 22:33:19 2 Tiny change: 'equired?\nQ2. Is t' -> 'equired?\n\nQ2. Is t'
en1 English akash_goel 2015-07-21 22:32:28 782 Initial revision (published)