20021201
Efficient parallel graph algorithms for coarsegrained multicomputers and BSP
Publication
Publication
Algorithmica , Volume 33  Issue 2 p. 183 200
In this paper we present deterministic parallel algorithms for the coarsegrained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following wellknown graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2edge connectivity and biconnectivity (testing and component computation). The algorithms require O(log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log(p)(N/p)). The algorithms assume that the local memory per processor (i.e., N/p) is larger than pε, for some fixed ε > 0. Our results imply BSP algorithms with O(log p) supersteps, O(g log(p)(N/P)) communication time, and O(log(p)(N/p)) local computation time. It is important to observe that the number of communication rounds/supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p. With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported. The algorithms for Problems (2)(7) are the first practically relevant parallel algorithms for these standard graph problems.
Additional Metadata  

Coarse grained parallel computing, Graph algorithms  
Algorithmica  
Organisation  School of Computer Science 
Dehne, F, Ferreira, A., Cáceres, E., Song, S.W., & Roncato, A. (2002). Efficient parallel graph algorithms for coarsegrained multicomputers and BSP. Algorithmica, 33(2), 183–200.
