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