A comparative study of maximum matching algorithms

Abstract

One of the central problems of discrete optimization is the problem of determining the maximal matching, which can be solved in various ways, depending on the structure of the initial data. In this article, a comparative study of the efficiency of maximal flow algorithms (Ford-Fulkerson) and the direct algorithm for determining maximal matching (Even & Kariv) on unweighted bipartite graphs is conducted. The analysis is based on a set of high-difficulty computing competition problems. Therefore, the results will be useful not only to those interested in the maximal matching problem but also to all those who are preparing to participate in various programming competitions.