MatchBG: A Boundary Subgraph-Based Maximal Matching Algorithm for Bipartite Graphs

Finding the maximum matching is a fundamental task in graph analysis with numerous applications, but the time complexity of the exact algorithms for this purpose is usually too high in practice. Therefore, using a maximal matching algorithm with lower time consumption to accelerate the exact algorithm has attracted significant attention. However, most existing research on maximal matching algorithms primarily focuses on quantity while overlooking quality. To address such problems, we propose a boundary subgraph-based rule to indicate what kind of matching is high-quality, and a maximal matching algorithm, MatchBG, to find such a matching. We evaluate MatchBG on real-life graphs. Extensive results demonstrate that MatchBG outperforms all other state-of-the-art maximal matching algorithms.