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 -