algorithmford-fulkerson

Calculate max flow efficiently using Ford Fulkerson after removing edge from the flow


Suppose that a maximum flow for G has been computed using Ford-Fulkerson, but an edge is now removed from E. how the maximum flow can be efficiently updated.


Solution

  • If the edge e you removed crosses the cut, then the maximum flow is equal to |f| − c(e), where |f| is the previously computed maximum flow and c(e) is the capacity of the removed edge.

    You can find detailed explanation here.