PARALLEL CONSTANT-TIME CONNECTIVITY ALGORITHMS ON A RECONFIGURABLE NETWORK OF PROCESSORS

abstract

• This short note presents constant-time algorithms for label- ing the connected components of an image on a network of processors with a wide reconfigurable bus. The algorithms are based on a processor indexing scheme which employs constant-weight codes. The use of such codes enables identifying a single representative processor for each component in a constant number of steps. The proposed algorithms can label an N x N image in 0(1) time using N2processors, which is optimal. Furthermore, the proposed techniques lead to an O(log N/log log N)-time image labeling algorithm on a network of N2 processors with a reconfigurable bus of width log N bits. It is shown that these techniques can be applied to labeling an undirected N-vertex graph represented by an adjacency matrix. 1995 IEEE

authors

• Alnuweiri, Hussein

published proceedings

• IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

author list (cited authors)

• ALNUWEIRI, H. M.

citation count

• 4

complete list of authors

• ALNUWEIRI, HM

publication date

• January 1995

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE Transactions on Parallel and Distributed Systems  Journal

keywords

• Array Processing
• Constant-time Algorithms
• Constant-weight Codes
• Graphs
• Image Computations
• Labeling Connected Components
• Parallel Processing
• Reconfigurable Networks Of Processors

Digital Object Identifier (DOI)

• 10.1109/71.363405

start page

• 105

end page

• 110

volume

• 6

issue

• 1

URL

• http%3A%2F%2Fdx.doi.org%2F10.1109%2F71.363405