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

An O(q^3 (q + d)n\log n) algorithm to find the connected components of G on a q-dimensional mesh-connected parallel computer and shows that the connected ones problem can be solved in time.

Abstract

Let $G = (V,E)$ be an undirected graph in which no vertex has degree more than d. Let $|V| = n^q = 2^q $ . In this paper we present an $O(q^3 (q + d)n\log n)$ algorithm to find the connected components of G on a q-dimensional $n \times n \times \cdots \times n$ mesh-connected parallel computer. When $d = 2$, the connected components can be found in $O(q^4 n)$ time. We also show that the connected ones problem can be solved in $O(q^6 n)$ time.