HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Engineering fast almost optimal algorithms for bipartite graph matching

Abstract : We consider the maximum cardinality matching problem in bipartite graphs. There are a number of exact, deterministic algorithms for this purpose, whose complexities are high in practice. There are randomized approaches for special classes of bipartite graphs. Random 2-out bipartite graphs, where each vertex chooses two neighbors at random from the other side, form one class for which there is an $O(m+n\log n)$-time Monte Carlo algorithm. Regular bipartite graphs, where all vertices have the same degree, form another class for which there is an expected $O(m + n\log n)$-time Las Vegas algorithm. We investigate these two algorithms and turn them into practical heuristics with randomization. Experimental results show that the heuristics are fast and obtain near optimal matchings. They are also more robust than the state of the art heuristics used in the cardinality matching algorithms, and are generally more useful as initialization routines.
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download

Contributor : Bora Uçar Connect in order to contact the contributor
Submitted on : Wednesday, July 1, 2020 - 12:29:30 PM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM


Files produced by the author(s)


  • HAL Id : hal-02463717, version 3



Ioannis Panagiotas, Bora Uçar. Engineering fast almost optimal algorithms for bipartite graph matching. ESA 2020 - European Symposium on Algorithms, Sep 2020, Pisa, Italy. ⟨hal-02463717v3⟩



Record views


Files downloads