BSP/CGM algorithm for maximum matching in convex bipartite graphs - Soares, J.; Stefanes, M. (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2003)
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.