VLSI Algorithms for the Connected Component Problem

This paper presents algorithms for the connected component problem that are suitable for VLSI implementation and use $o(n^2 )$ area. Two VLSI models, which differ in the number of input/output ports allowed to be placed on the boundary of the chip, are considered. It is shown how to achieve a continuous area-time tradeoff of $AT^2 = O(n^4 )$ in the range $\Omega (n) = A = o(n^2 )$. This tradeoff is optimal for one model, and for the other model continuous tradeoffs of the form $AT = O(n^{5/2} )$ in the range $\Omega (n) = A = O(n^{5/4} )$ and $AT^3 = O(n^5 )$ in the range $\Omega (n^{5/4} ) = A = o(n^2 )$ are exhibited.