Characterizations of max-balanced flows
type: Item
instance of: scholarly article
title: Characterizations of max-balanced flows
zbMATH Open document ID: 0769.05044
DOI: 10.1016/0166-218X(92)90179-E
author: Uriel G. Rothblum
author: Hans Schneider
author: Michael H. Schneider
published in: Discrete Applied Mathematics
publication date: 1993-01-17T00:00:00Z
review text: Let \(G=(V,A)\) be a directed graph. Then a flow for \(G\) is an arbitrary real-valued function defined on the arc set \(A\). A flow \(f\) is called max-balanced if, for any \(\varnothing\subsetneqq W\subsetneqq V\), it holds \(\max_{x\in W^ +}f(x)=\max_{x\in W^ -}f(x)\), where \(W^ +\) \((W^ -)\) is the set of all arcs \(x=(u,v)\) with \(v\in W^ +\), \(u\notin W^ +\) \((u\in W^ -,v\notin W^ -)\). Ten characterizations of max- balanced flows are given.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 98503
zbMATH Keywords: max-balanced flow
zbMATH Keywords: directed graph
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: Algebraic and combinatorial methods in operations research. Proceedings of the Workshop on Algebraic Structures in Operations Research
cites work: Q3942759
cites work: Minimax algebra
cites work: Line-sum-symmetric scalings of square nonnegative matrices
cites work: Diagonal similarity and equivalence for matrices over groups with 0
cites work: Algebraic flows in regular matroids
cites work: Q3922498
cites work: Minimal cost flows in regular matroids
cites work: Decomposition of group flows in regular matroids
cites work: An analogue of Hoffman's circulation conditions for max-balanced flows
cites work: On abstract dual linear programs
cites work: The spectrum of a nonlinear operator associated with a matrix
cites work: Computing optimal scalings by parametric network algorithms
cites work: Q3730336
cites work: Scalings of matrices which have prespecified row sums and column sums via optimization
cites work: Scaling Matrices to Prescribed Row and Column Maxima
cites work: Matrix scaling, entropy minimization, and conjugate duality. I: Existence conditions
cites work: Q3032292
cites work: Max-Balancing Weighted Directed Graphs and Matrix Scaling
cites work: A Comparative Study of Algorithms for Matrix Balancing
cites work: Faster parametric shortest path and minimum‐balance algorithms
cites work: Duality for algebraic linear programming
cites work: Linear and combinatorial optimization in ordered algebraic structures
full work available at URL: 0166-218x(92)90179-e
OpenAlex ID: W1991285975
description: scientific article; zbMATH DE number 98503