Sensitivity Analysis of Multiterminal Flow Networks

Given an undirected flow network with finite arc capacities, an algorithm is developed for the determination of the effect of a reduction (or increase) in the capacity of any arc on the maximum flow between any two nodes of the network. The algorithm is based on the Gomory-Hu construction of “cut-trees.”