Performance Evaluation of Maximum Matching Algorithm Implementations

The maximum matching problem is a fundamental challenge in graph theory, with applications in network design and resource allocation. This study evaluates the performance of multiple maximum matching algorithm implementations across distincti classes of matching problems. To assess efficiency, we design specialized test set "courses" that highlight key graph features, such as density and vertex count. Evaluating algorithms performance on these courses, our results indicate that Hopcroft-Karp was the most efficient algorithm we have implemented for solving bipartite graphs, while hypergraph solvers seem to work effectively on only some sets of problems.