# Algorithm Problem

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.

See attached file for full problem description.

© BrainMass Inc. brainmass.com October 9, 2019, 6:57 pm ad1c9bdddfhttps://brainmass.com/computer-science/searching/algorithm-problem-103222

#### Solution Preview

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?

Answers:

The running time is: O(V E) because: the running time is O(E | f*|), and | f*| = O (V) because the ﬂow is bounded by the capacity of any cut, and the capacity of the cut (s, V − s) is O(V ) because there are O(V ) edges leaving s, and ...

#### Solution Summary

Algorithm Problem is solved.