Explore BrainMass
Share

# Algorithm Problem

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e &#61646; E has capacity c(e) = 1. Assume also, for convenience, that |E| = &#61527; (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.

https://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?