Volume 13, Number 03, February 2023

A DFS Algorithm for Maximum Matchings in General Graphs

  Authors

Tony T. Lee, Bojun Lu and Hanli Chu, The Chinese University of Hong Kong, China

  Abstract

In this paper, we propose a depth-first search (DFS) algorithm for finding maximum matching in general graphs. Unlike blossom shrinking algorithms, which store all possible alternative alternating-paths in the super-vertices shrinking from blossoms, the newly proposed algorithm does not involve blossom shrinking. The basic idea is to deflect the alternating path when facing blossoms. The algorithm maintains detour information in an auxiliary stack to minimize the redundant data structures. A benefit of our technique is to avoid spending the time on shrinking and expanding blossoms. This DFS algorithm can determine a maximum matching of a general graph with m edges and n vertices in 𝑂(𝑚𝑛) time with space complexity 𝑂(𝑛).

  Keywords

Maximum Matching, Augmenting Path, Blossom, Trunk, Sprout.