## Abstract

This paper presents a VLSI array for labeling the connected components of a graph on N nodes in O(r) steps using a reconfigurable bus of width m bits, such that (_{r}^{m})≥N and 1≤r≤m. The network architecture consists of an array of simple logic nodes which are connected by a reconfigurable bus.To solve a problem on N nodes, the array uses N processors and N(N-1)/2 switches. The proposed connectivity and transitive closure algorithms are based on a processor indexing scheme which employs constant-weight codes. It is shown that when r is a constant, then the algorithm takes O(1) time using a bus of width O(N^{1/r}), and when r = [log N/loglog N], the algorithm takes O(log N/loglog N) time using a bus or width O(log N) bits.

Original language | English |
---|---|

Pages (from-to) | 105-115 |

Number of pages | 11 |

Journal | Parallel Processing Letters |

Volume | 4 |

Issue number | 1-2 |

Publication status | Published - Jun 1994 |

Externally published | Yes |