About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Networks
Paper
Sensitivity analysis of 0‐1 multiterminal network flows
Abstract
Given an undirected 0‐1 flow network G with n nodes, Gomory and Hu's algorithm solves the multiterminal maximum flow problem by constructing a cut‐tree for G. Their algorithm requires solving n − 1 maximum flow problems. A perturbed network of G is a network generated from G by deleting or adding an edge to G. For a given network G and an edge s, t to be deleted from (resp., added to) G, a marginal cut‐tree T is a cut‐tree for G from which a cut‐tree for the perturbed network can be generated easily by reducing (resp., increasing) by 1 the weight of every edge in the path between s and t in T. Given an undirected 0‐1 flow network G, a cut‐tree for G, and an edge to be deleted from or added to G, we present an algorithm to generate a cut‐tree for the perturbed network by first transforming the given cut‐tree for G into a marginal cut‐tree and then transforming the marginal cut‐tree into a cut‐tree for the perturbed network. This algorithm also requires solving the maximum flow problem; depending on the input data, the number of such problems to be solved is between 0 and n − 2 for edge deletion and between 0 and n − 1 for edge addition. Properties on the input data that lead, respectively, to the best‐case and worst‐case complexities of the algorithm are identified, and numerical experiments are included. Copyright © 1991 Wiley Periodicals, Inc., A Wiley Company