On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
type: Item
instance of: scholarly article
title: On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
zbMATH Open document ID: 0685.90039
DOI: 10.1016/0020-0190(89)90087-2
author: Hiroshi Nagamochi
author: Toshihide Ibaraki
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: We study the condition for a class of directed networks, under which the max-flow min-cut property for the multicommodity flow problem implies the integral flow property. Let \({\mathcal N}\) denote the set of all directed networks \(N=(G,P,g,c)\) defined as follows. G(A,V): A finite directed graph, where V is a set of nodes, and A is a set of directed arcs. P: A set of source-sink ordered pairs \((s^ k,t^ k)\), \(k=1,2,...,K\), g: \(\{1,2,...,K\}\to {\mathbb{Z}}^+\) \((=\) the set of nonnegative integers). c: \(A\to {\mathbb{Z}}^+\) is a capacity function of arcs. The multicommodity flow problem in a directed network \(N\in {\mathcal N}\) is feasible if there exists a flow f: \(A\times \{1,2,...,K\}\to {\mathbb{R}}^+\) \((=\) the set of nonnegative real numbers), which satisfies the flow conservation law and the side capacity constraint. A flow f is called an integral flow if \(f(a,k)\to {\mathbb{Z}}^+\) for all \(a\in A\), \(k=1,2,...,K.\) A class of networks \(Q\subseteq {\mathcal N}\) has the integral flow property if there exists an integral flow for any feasible network N in Q. A class of networks \(Q\subseteq {\mathcal N}\) has the max-flow min-cut property if any network N in Q is feasible if and only if the cut condition holds. A class \(Q\subseteq {\mathcal N}\) is called capacity and demand independent if, for any network \(N=(G(V,A),P,g,c)\) in Q, every network \(N'=(G,P,g',c')\) with \(g\geq g'\geq 0\) and \(c\geq c'\geq 0\) (the sign \(\geq\) between two vectors means inequality in every component) also belongs to class Q. Then, we can prove that if a capacity and demand independent class \(Q\subseteq {\mathcal N}\) has the max-flow min-cut property, then Q satisfies the integral flow property.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 4123496
zbMATH Keywords: directed networks
zbMATH Keywords: max-flow min-cut property
zbMATH Keywords: multicommodity flow problem
zbMATH Keywords: integral flow property
zbMATH Keywords: flow conservation
zbMATH Keywords: side capacity constraint
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90087-2
OpenAlex ID: W2085443931
cites work: Q5595961
cites work: A new polynomial-time algorithm for linear programming
cites work: Q3050157
cites work: Multicommodity flows in planar graphs
cites work: Multicommodity flows in graphs
cites work: A dual version of Tardos's algorithm for linear programming
cites work: On Odd Cuts and Plane Multicommodity Flows
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
description: scientific article; zbMATH DE number 4123496