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).
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?
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.
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.
Computer Science Homework Solutions
#103222
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.
What is this?
By OTA - Overall OTA Rating
Xiao Liu, MS - 4.7/5
Purchase Cost Now
$2.19 CAD (was ~$19.95)
Included in Download
- Plain text response
- Attached file(s):
- Let+G.doc
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- This is a problem about Network Flows. - see attachment
- Single Source Longest-Path Problem - Single Source Longest-Path Problem • A longest-path problem can be transformed into a shortest path problem by changing the sign of all weights • Alternatively, the Bellman-Ford algorithm can be ...
- Describe an efficient algorithm to determine the depth of a comparison network with given representation. - Mr. Johnson draws an n-input comparison network with m comparators according to the following conventions. The lines of the network go left-to-right, and comparators are drawn vertically to connect ...
- Mathematical Properties of Binary Trees - ----------- Show that if binary tree T is full at level i, then it is full at every level j smaller than i. --------------- Show that the depth of the complete binary tree Tn for a general n ...
- Edge connectivity - The edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge conn ...
