BSP/CGM algorithm for maximum matching in convex bipartite graphs
J. Soares, Marco A. Stefanes · 2004
A bipartite graph G = (V,W,E) is convex if there exists an ordering of the vertices of W such that, for each v /spl isin/ V, the neighbors of v are consecutive in W. We describe a BSP/CGM algorithm for finding a maximum matching in a convex bipartite graph. For p processors, the algorithm runs in time O((|V|/p)lg(|V|/p)lgp) and it uses O(lgp) communication rounds.