Premium
Sensitivity analysis of 0‐1 multiterminal network flows
Author(s) -
Lin Shiow C.,
Ma Eva
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210703
Subject(s) - steiner tree problem , tree (set theory) , maximum flow problem , enhanced data rates for gsm evolution , mathematics , minimum cut , flow network , tree network , combinatorics , flow (mathematics) , sensitivity (control systems) , algorithm , path (computing) , k ary tree , tree structure , computer science , time complexity , binary tree , geometry , artificial intelligence , electronic engineering , engineering , programming language
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.