Maximum concurrent flows and minimum cuts
type: Item
instance of: scholarly article
title: Maximum concurrent flows and minimum cuts
zbMATH Open document ID: 0762.90024
DOI: 10.1007/BF01758845
author: S. Singh
published in: Algorithmica
publication date: 1992-09-27T00:00:00Z
review text: Let \(f(X,\overline X)\) be any symmetric function representing the cost of cuts \((X,\overline X)\) in a network. The authors show the \(n-1\) minimum cost cuts are always sufficient to separate all pairs of nodes, and they propose an algorithm to find the set of these essential cuts with \(n-1\) oracle calls [improving the result of \textit{R. Hassin}, Math. Oper. Res. 13, No. 4, 535-542 (1988; Zbl 0667.90034)]. The authors also consider \(k\)-way partitions, and, using linear programming techniques, prove the following result (independently obtained with combinatorial arguments by \textit{F. Shahrokhi} and \textit{D. W. Matula} [``The maximum concurrent flow problem'', Tech. Rep., New Mexico Tech. (1986)]): If the saturated arcs in a multicommodity flow problem form a \(k\)-way partition, \(k\leq 4\), then the \(k\)-way partition contains a two-way partition, which is the minimum weight sparsest cut.
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 64259
zbMATH Keywords: minimum cost cuts
zbMATH Keywords: \(k\)-way partitions
zbMATH Keywords: multicommodity flow
reviewed by: Patrick Jaillet
MaRDI profile type: Publication
cites work: Q3323698
cites work: Maximal Flow Through a Network
cites work: A suggested computation for maximal multi-commodity network flows
cites work: Multi-Terminal Network Flows
cites work: Multi-terminal maximum flows in node-capacitated networks
cites work: Solution Bases of Multiterminal Cut Problems
cites work: Multi-Commodity Network Flows
cites work: Circular Cuts in a Network
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: Combinatorial approaches to multiflow problems
cites work: The maximum concurrent flow problem
full work available at URL: https://doi.org/10.1007/bf01758845
OpenAlex ID: W2001646664
description: scientific article; zbMATH DE number 64259