Parametric analysis of overall min-cuts and applications in undirected networks

✍ Scribed by Y.P. Aneja; R. Chandrasekaran; K.P.K. Nair

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 211 KB
• Volume: 85
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00364-2

✦ Synopsis

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 , λ}, where λ is a parameter ranging from 0 to ∞. Letting function v(λ) denote the min-cut capacity, we develop an algorithm to describe v(λ) which involves at most n applications of Stoer and Wagner scheme, where n denotes the number of nodes in the network. We use v(λ) to determine an overall min-cut for multiroute flows as defined by Kishimoto. Such multi-route flows have interesting applications in communication networks.