TY - JOUR
T1 - A New Class of Parallel Algorithms for Finding Connected Components on Machines with Bit-Vector Operations
AU - Liang, Y.
AU - Dhall, S. K.
AU - Lakshmivarahan, S.
N1 - The problem of developing serial and parallel algorithms for finding connected components of an undirected graph G = ( V, E) has received considerable attention in the literature. If and , the well-known serial algorithm takes O( n + m) steps.
PY - 1994
Y1 - 1994
N2 - Abstract The problem of developing serial and parallel algorithms for finding connected components of an undirected graph G = (V, E) has received considerable attention in the literature. If ¦V¦ = n and ¦E¦ = m , the well-known serial algorithm takes O(n + m) steps. The first parallel algorithm for this problem was reported by Arjomandi and Corneil and takes T k + L[log k] + 2n steps using k processors, where T is the complexity of optimal sequential breadth first search and L is bounded by the diameter of the graph. Using a CREW (concurrent read and exclusive write) model, Chandra proposed a parallel algorithm that takes O(log2n) steps using O( n log7 logn ) processors. Following this lead, a number of parallel algorithms requiring the same time bound but different processor bounds have been reported by many authors. In this paper we use a machine model that performs (componentwise) bit vector operations (such as conjunction, comparison, etc.) in parallel. Using this model we show that the connected components of a graph G can be found in OB(n log n) steps serially, where OB refers to the number of bit vector operations. Thus, for dense graphs this serial algorithm performs better than the algorithm that is based on the depth first search. We also show that finding connected components on a CREW model takes OB(log2 n) steps using only n log n processors, and on a CRCW model, it takes OB((log n)· (log log n)) steps using only n processors. These algorithms have larger processor efficiency compared to all the known algorithms and are particularly attractive for the dense graphs when a small number of processors are available
AB - Abstract The problem of developing serial and parallel algorithms for finding connected components of an undirected graph G = (V, E) has received considerable attention in the literature. If ¦V¦ = n and ¦E¦ = m , the well-known serial algorithm takes O(n + m) steps. The first parallel algorithm for this problem was reported by Arjomandi and Corneil and takes T k + L[log k] + 2n steps using k processors, where T is the complexity of optimal sequential breadth first search and L is bounded by the diameter of the graph. Using a CREW (concurrent read and exclusive write) model, Chandra proposed a parallel algorithm that takes O(log2n) steps using O( n log7 logn ) processors. Following this lead, a number of parallel algorithms requiring the same time bound but different processor bounds have been reported by many authors. In this paper we use a machine model that performs (componentwise) bit vector operations (such as conjunction, comparison, etc.) in parallel. Using this model we show that the connected components of a graph G can be found in OB(n log n) steps serially, where OB refers to the number of bit vector operations. Thus, for dense graphs this serial algorithm performs better than the algorithm that is based on the depth first search. We also show that finding connected components on a CREW model takes OB(log2 n) steps using only n log n processors, and on a CRCW model, it takes OB((log n)· (log log n)) steps using only n processors. These algorithms have larger processor efficiency compared to all the known algorithms and are particularly attractive for the dense graphs when a small number of processors are available
UR - https://www.sciencedirect.com/science/article/abs/pii/0020025594900094
U2 - 10.1016/0020-0255(94)90009-4
DO - 10.1016/0020-0255(94)90009-4
M3 - Article
SN - 0020-0255
VL - 76
JO - Information Sciences
JF - Information Sciences
ER -