Algorithmes rapides quasi-optimaux pour trouver des couplages dans de graphes bipartis

International audience; 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 randomfrom 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.