Carleton University
Technical Report TR-99-04
January 1999
Coarse Grained Parallel Maximum Matching In Convex Bipartite Graphs
P. Bose, A. Chan, Frank Dehne, M. Latzel
Abstract
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 Oh(log p) communication rounds and Oh(T_sequ(n/p,m/p) + n/p log p) local computation, where n = |A|, m = |B| and T_sequ(n,m) is the sequential time complexity for the problem. For the BSP model, this implies O(log p) supersteps with O(gN +g n/p log p) communication cost and O(T_sequ(n/p,m/p) + n/p log p) local computation.