Efficient parallel graph algorithms for
coarse grained multicomputers and BSP
E. Caceres, F. Dehne, A. Ferreira, P. Flocchini, I. Rieping, A. Roncato,
N. Santoro, and S. W. Song
April 1997
Abstract
In this paper, we present {\em deterministic} parallel algorithms for the coarse grained
multicomputer (CGM) and bulk-synchronous parallel computer (BSP) models which solve the
following well known graph problems: (1) list ranking, (2) Euler tour construction, (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, (7) 2-edge connectivity and biconnectivity (testing and component computation),
and (8) cordal graph recognition (finding a perfect elimination ordering). The algorithms for
Problems 1-7 require $O(\log p)$ communication rounds and linear sequential work per round.
Our results for Problems 1 and 2 hold for arbitrary ratios $\frac{n}{p}$, i.e. they are {\it fully
scalable}, and for Problems 3-8 it is assumed that $\frac{n}{p} \geq p^{\epsilon}$, $\epsilon >
0$, which is true for all commercially available multiprocessors. We view the algorithms presented
as an important step towards the final goal of $O(1)$ communication rounds. Note that, the
number of communication rounds obtained in this paper is independent of $n$ and grows only very
slowly with respect to $p$. Hence, for most practical purposes, the number of communication
rounds can be considered as constant. The result for Problem 1 is a considerable improvement
over those previously reported. The algorithms for Problems 2-7 are the first practically relevant
deterministic parallel algorithms for these problems to be used for commercially available coarse
grained parallel machines.
Full paper
in compressed Postscript format.