BSP/CGM algorithm for maximum matching in convex bipartite graphs

• J. Soares USP
• M. Stefanes UFMS

Resumo

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.

Palavras-chave: User-generated content, Bipartite graph, Computer architecture, High performance computing