Parametric analysis of overall min-cuts and applications in undirected networks. (Q1853178)

The overall min-cut problem in a capacitated undirected network is well known. Recently Stoer and Wagner gave an elegant algorithm for finding such a cut. In this paper we present a parametric analysis of such a cut where the capacity of an arc \({i,j}\) in the network is given by \(\min{b_{ij},\lambda}\), where \(\lambda\) is a parameter ranging from \(0\) to \(\infty\). Letting function \(v(\lambda)\) denote the min-cut capacity, we develop an algorithm to describe \(v(\lambda)\) which involves at most \(n\) applications of Stoer and Wagner scheme, where \(n\) denotes the number of nodes in the network. We use \(v(\lambda)\) to determine an overall min-cut for multiroute flows as defined by Kishimoto. Such multi-route flows have interesting applications in communication networks.