Paper Info
Title
Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP
Abstract
In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel(BSP) models for solving the following well-known 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) com- puting an ear decomposition or open ear decomposition, and (7) 2-edge 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.
Year
DOI
Venue
1997
10.1007/3-540-63165-8_195
ICALP
Keywords
Field
DocType
coarse grained multicomputers,efficient parallel graph algorithms,graph algorithms.,coarse grained parallel computing,bulk synchronous parallel,lowest common ancestor,connected component,parallel algorithm,parallel computer
Discrete mathematics,List ranking,Combinatorics,Lowest common ancestor,Parallel algorithm,Computer science,Computational geometry,Chordal graph,Eulerian path,Ear decomposition,Connected component,Distributed computing
Conference
Volume
ISSN
ISBN
1256
0302-9743
3-540-63165-8
Citations 
PageRank 
References 
60
2.78
28
Authors
8
Name
Order
Citations
PageRank
Edson Cáceres11208.82
Frank K. H. A. Dehne21211146.07
Afonso Ferreira317115.95
Paola Flocchini42421157.13
Ingo Rieping51709.85
Alessandro Roncato632020.21
N. Santoro7101788.05
Siang W Song816514.69