2022/11/01 by Sylvain Guillemot, Guillemot, Sylvain
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2211.00711
openalex publication_date 2022/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
If G is a bipartite graph, Hall's theorem \citeH35 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.