We present a coarse grained parallel algorithm for computing a maximum matching in a convex bipartite graph G = (A, B, E). For p processors with N/p memory per processor, N = |A|+|B|, N/p≥p, the algorithm requires O(log p) communication rounds and O(Tsequ(n/p, m/p)+n/p log p) local computation, where n = |A|, m = |B| and Tsequ (n, m) is the sequential time complexity for the problem. For the BSP model, this implies O(log p) supersteps with O(gN+gn/p log p) communication cost and O(Tsequ(n/p, m/p)+n/p log p) local computation.

Proceedings of the 1999 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing
School of Computer Science

Bose, P, Chan, A. (A.), Dehne, F, & Latzel, M. (M.). (1999). Coarse grained parallel maximum matching in convex bipartite graphs. Proceedings of the International Parallel Processing Symposium, IPPS, 125–129.