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

https://hal.inria.fr/hal-02463717
Contributor : Bora Uçar <>
Submitted on : Wednesday, July 1, 2020 - 12:29:30 PM
Last modification on : Thursday, July 2, 2020 - 3:46:23 AM

File

ipbuESA20.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02463717, version 3

Collections

Citation

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⟩

Share

Metrics

Record views

50

Files downloads

119