Minimal cost flows in regular matroids

Rainer Ernst Burkard*, H. Hamacher

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


In this paper flows in regular matroids M are considered and three algorithms are described for determining maximal matroid flows with minimal costs. The first algorithms starts with an arbitrary maximal matroid flow and reduces its costs by finding negative circuits in M. The second builds up a min cost matroid flow by starting with the zero flow and performing augmentations along shortest augmenting circuits. The last algorithm works in regular matroids with special structures. By a sequence of admissible transformations an optimal matroid flow can be found. This transformation method can be viewed as a generalization of the Hungarian Method for solving linear assignment problems. The arguments used in the paper are of pure combinatorial kind and don’t make any use of the representation of the regular matroid M by a totally unimodular matrix.
Original languageEnglish
Pages (from-to)32-47
JournalMathematical Programming
Issue number1
Publication statusPublished - 1981
Externally publishedYes

Cite this