论文标题
两分匹配的替代多项式时间算法
Alternative polynomial-time algorithm for Bipartite Matching
论文作者
论文摘要
如果$ g $是两部分图，则Hall的定理\ cite {H35}为存在覆盖两者一侧的$ g $的匹配条件提供了条件。该定理承认了一种众所周知的算法证明，涉及对增强道路的反复搜索。我们在这里使用该问题的游戏理论公式提出了一种替代算法。我们还展示了如何将此公式扩展到平衡超图的设置。
If $G$ is a bipartite graph, Hall's theorem \cite{H35} gives a condition for the existence of a matching of $G$ covering one side of the bipartition. This theorem admits a well-known algorithmic proof involving the repeated search of augmenting paths. We present here an alternative algorithm, using a game-theoretic formulation of the problem. We also show how to extend this formulation to the setting of balanced hypergraphs.
