Finding Connected Components and Connected Ones on a Mesh-Connected Parallel Computer

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)nlog 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.