论文标题
DFS算法，用于一般图中的最大匹配
A DFS Algorithm for Maximum Matchings in General Graphs
论文作者
论文摘要
在本文中，我们提出了一种深度优先搜索（DFS）算法，以在一般图中搜索最大匹配。与花朵缩小算法不同，在超级媒体中存储了所有可能的替代交替路径，从花朵从花朵缩小的算法中，新提出的算法不涉及开花收缩。基本思想是在面对开花时偏转交替的路径。该算法在辅助堆栈中维护弯路信息，以最大程度地减少冗余数据结构。我们技术的好处是避免花时间在缩小和扩大花朵上。该DFS算法可以确定具有$ m $边缘的常规图和$ n $ Vertices的最大匹配，$ o（mn）$ time带有空间复杂性$ o（n）$。
In this paper, we propose a depth-first search (DFS) algorithm for searching maximum matchings in general graphs. Unlike blossom shrinking algorithms, which store all possible alternative alternating paths in the super-vertices shrunk 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 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 $O(mn)$ time with space complexity $O(n)$.
