STATIC AND DYNAMIC PARALLEL COMPUTATION OF CONNECTED COMPONENTS

Authors
FERRAGINA P
Citation
P. Ferragina, STATIC AND DYNAMIC PARALLEL COMPUTATION OF CONNECTED COMPONENTS, Information processing letters, 50(2), 1994, pp. 63-68
Citations number
16
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
50
Issue
2
Year of publication
1994
Pages
63 - 68
Database
ISI
SICI code
0020-0190(1994)50:2<63:SADPCO>2.0.ZU;2-#
Abstract
The connected components of an undirected graph are determined in the EREW model with p processors, using a parallel extension of the ''spar sification'' technique. A previous algorithm due to Kruskal et al. is optimal for p less-than-or-equal-to ml/(2+epsilon) < n/2. We show that our algorithm is work-optimal for an extended range of values. Using the ''sparsification'' tree data structure we provide also a dynamic a lgorithm to maintain the connectivity property of a graph as edges are inserted and deleted.