Programming in Networks and Graphs: On the Combinatorial Background and Near-Equivalence of Network Flow and Matching Algorithms

Network flow and matching are often treated separately in the literature and for each class a variety of different algorithms has been developed. These algorithms are usually classified as primal, dual, primal—dual etc. The question the author addresses in this work is that of the existence of a common combinatorial principle which might be inherent in all those apparently different approaches. It is shown that all common network flow and matching algorithms implicitly follow the so—called ...