Maximum concurrent flows and minimum cuts (Q1194345)

From MaRDI portal
Revision as of 19:49, 14 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Maximum concurrent flows and minimum cuts
scientific article

    Statements

    Maximum concurrent flows and minimum cuts (English)
    0 references
    0 references
    0 references
    27 September 1992
    0 references
    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.
    0 references
    minimum cost cuts
    0 references
    \(k\)-way partitions
    0 references
    multicommodity flow
    0 references

    Identifiers