An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. On input a flow network G, you ran Ford-Fulkerson and computed a maximum flow f.

i. Give an efficient algorithm that finds a critical edge in G.

ii. Give an efficient algorithm that finds every critical edge in G.

Question

Kaylyn Knight

Mathematics

14 June, 02:57

An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. On input a flow network G, you ran Ford-Fulkerson and computed a maximum flow f.

i. Give an efficient algorithm that finds a critical edge in G.

ii. Give an efficient algorithm that finds every critical edge in G.

+2

Answers (1)

Know the Answer?

Pierce Lawrence · Answer 1

Begin find the residual graph of the graph G (V, E) using ford Fulkerson For each edge u, v in the residual graph such that u, v is not in the residual graph and also not in G Apply DFS to see if u has no path to v then return edge (u, v) else nothing end