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