Parametric analysis of overall min-cuts and applications in undirected networks.
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.
- Parametric min-cuts analysis in a network.
- Minimum cuts in parametric networks
- Revisiting parametric multi-terminal problems: maximum flows, minimum cuts and cut-tree computations
- A fast algorithm for the generalized parametric minimum cut problem and applications
- A faster parametric minimum-cut algorithm
- A Fast Parametric Maximum Flow Algorithm and Applications
- A simple min-cut algorithm
- scientific article; zbMATH DE number 1256704 (Why is no real title available?)
- scientific article; zbMATH DE number 961880 (Why is no real title available?)
- Maximizing residual flow under an arc destruction
- Minimal ratio spanning trees
- Network flows. Theory, algorithms, and applications.
- Parametric min-cuts analysis in a network.
This page was built for publication: Parametric analysis of overall min-cuts and applications in undirected networks.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853178)
