Invariant sets of arcs in network flow problems
type: Item
instance of: scholarly article
title: Invariant sets of arcs in network flow problems
zbMATH Open document ID: 0585.90029
DOI: 10.1016/0166-218X(86)90063-6
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: Assume a standard network flow problem. The set \(A=A^+\cup A^-\) of arcs is said to be invariant if there exists a constant c so that for every max flow x \[ \sum \{x(a);\quad a\in A^+\}-\sum \{x(a);\quad a\in A^-\}=c. \] The main result of the paper reads as follows: Let \(A=A^+\cup A^-\) be a set of arcs. If there exists a cut \((S,\bar S)\) such that \(A^+\subseteq (S,\bar S)\), \(A^-\subseteq (\bar S,S)\) or \(A^+\subseteq (\bar S,S)\), \(A^-\subseteq (S,\bar S)\) with \(((S,\bar S)\cup (\bar S,S))\setminus A\) consisting of invariant arcs, then A is an invariant set of arcs. Conversely, if \(A=A^+\cup A^-\) is a minimal invariant set of arcs, then such a cut \((S,\bar S)\) exists. This assertion is applied to \((0,1)\)-matrices with given row and column sums and some new results are obtained.
reviewed by: Mirko Křivánek
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3939061
zbMATH Keywords: flows in networks
zbMATH Keywords: network flow problem
zbMATH Keywords: invariant set of arcs
zbMATH Keywords: (0,1)- matrices
author: R. P. Anstee
MaRDI profile type: Publication
cites work: The network flows approach for matrices with given row and column sums
cites work: Matrices of zeros and ones with fixed row and column sum vectors
cites work: Invariant Sets for Classes of Matrices of Zeros and Ones
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Q5514188
full work available at URL: 0166-218x(86)90063-6
OpenAlex ID: W2009174518
description: scientific article; zbMATH DE number 3939061