Explore BrainMass
Share

Explore BrainMass

    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  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 ad1c9bdddf
    https://brainmass.com/computer-science/searching/algorithm-problem-103222

    Attachments

    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 flow 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.

    $2.19