Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e E has capacity c(e) = 1. Assume also, for convenience, that |E| = (V).
a. Suppose we implement the Ford-Fulkerson maximum-flow algorithm by using depth-first search to find augmenting paths in the residual graph. what is the worst-case running time of this algorithm on G?
b. Suppose a maximum flow for G has been computed, and a new edge with unit capacity is added to E. Describe how the maximum flow can be efficiently updated. (Note: It is not the value of the flow that must be updated, but the flow itself.) Analyze your algorithm.
c. Suppose a maximum flow for G has been computed, but an edge is now removed form E. Describe how the maximum flow can be efficiently updated. Analyze your algorithm.