Coarse grained parallel maximum matching in convex bipartite graphs
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.
|Conference||Proceedings of the 1999 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing|
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.