Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes

DOI10.1287/moor.12.1.72zbMath0616.90014OpenAlexW2070851851MaRDI QIDQ4726018

Klaus Truemper

Publication date: 1987

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.12.1.72

zbMATH Keywords

polynomial time algorithmsconnected binary matroid

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

A decomposition theory for matroids. III. Decomposition conditions, A survey on flows in graphs and matroids, Matrices with the Edmonds-Johnson property, A construction for binary matroids, Recognizing max-flow min-cut path matrices, Covering Vectors by Spaces: Regular Matroids, Generalizing the all-pairs min cut problem, A short proof of the Truemper-Tseng theorem on max-flow min-cut matroids, Ranking tournaments with no errors. II: Minimax relation, Single Commodity-Flow Algorithms for Lifts of Graphic and CoGraphic Matroids, A decomposition of the matroids with the max-flow min-cut property, Combinatorial optimization with 2-joins