Title :
BSP/CGM algorithm for maximum matching in convex bipartite graphs
Author :
Soares, Jose ; Stefanes, Marco
Author_Institution :
Dept. de Ciencia da Computacao, Sao Paulo Univ., Brazil
Abstract :
A bipartite graph G = (V,W,E) is convex if there exists an ordering of the vertices of W such that, for each v ∈ 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.
Keywords :
computational complexity; directed graphs; multiprocessing systems; optimisation; parallel algorithms; BSP/CGM algorithm; computational complexity; convex bipartite graphs; maximum matching; multiprocessing systems; optimisation; Bipartite graph; Computer architecture; High performance computing; User-generated content;
Conference_Titel :
Computer Architecture and High Performance Computing, 2003. Proceedings. 15th Symposium on
Print_ISBN :
0-7695-2046-4
DOI :
10.1109/CAHPC.2003.1250335
