2

Suppose that a maximum flow for G has been computed using Ford-Fulkerson, and a new edge with unit capacity is added to E. How the maximum flow can be efficiently updated. (t is not the value of the flow that must be updated, but the flow itself.

Arsalan Mehmood
  • 35
  • 10
  • 2
    Try to find an augmenting path that uses the new edge. You will need linear time to do it (one DFS) – Niklas B. Dec 08 '16 at 17:42
  • Can you show us the code written till now to calculate the max flow of an initial graph without considering the new edge that gets added?? – User_Targaryen Dec 08 '16 at 18:04
  • i have not written any code so far just want ti make it clear theoretically. But I am using Ford Fulkerson algorithm .... – Arsalan Mehmood Dec 08 '16 at 18:19
  • Although Niklas B.'s comment basically is the solution, one could also try to maintain the minimum cut along the calculation. If the added edge is not in the cut, the maximum flow has not changed. – Codor Dec 08 '16 at 18:27
  • alright... i am getting the point. can you please explain what is mean by the term "undone" here in the following link, http://stackoverflow.com/questions/27455970/update-maximum-flow-after-adding-an-edge – Arsalan Mehmood Dec 08 '16 at 18:35

1 Answers1

0

Let G' be the graph with the new edge e added to G. Note that we retain the capacity and flow for the remaining edges.

Now find an augmenting path p in G'.

If p exists, then update the flow along that path in G' by 1. Otherwise, the flow remains the same.

This gives the final flow values. This is correct because if p exists, then it passes through e. Hence, the flow update along p is exactly by 1. Since Folk-Fulkerson algorithm increases the flow in integral steps, there is no augmenting path in G' after this update.

If p doesn't exist, then by the mincut-maxflow argument, this is the maximum flow as the mincut is 0.

foo
  • 166
  • 9