# Engineering fast almost optimal algorithms for bipartite graph matching

1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [41 references]

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

### 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⟩

Record views