Key points are not available for this paper at this time.
Let G = (V, E) be an undirected graph in which no vertex has degree more than d. Let |V| = nq = 2q. In this paper we present an O (q³ (q + d) n n) algorithm to find the connected components of G on a q-dimensional n n n mesh-connected parallel computer. When d = 2, the connected components can be found in O (q⁴ n) time. We also show that the connected ones problem can be solved in O (q⁶ n) time.
Nassimi et al. (Sat,) studied this question.