Complete Binary Spanning Trees of the Eight Nearest Neighbor Array
- 1 June 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (6) , 547-549
- https://doi.org/10.1109/TC.1985.5009406
Abstract
Complete binary spanning trees of an n x n array of processors with an eight nearest neighbor interconnection pattern exist for a limited value of n. These spanning trees provide a fast route to accumulate information from all processors of the array, and allow certain problems to be solved as efficiently on an eight-neighbor array as on a tree-structured array. The condition under which complete binary spanning trees of a square array may exist is determined. This condition shows that complete binary spanning trees of an n x n eight-neighbor array exist only for n ≪ = 13. It is also observed that for n ≪ = 6, leaf nodes of these spanning trees lie on the periphery of the array.Keywords
This publication has 7 references indexed in Scilit:
- Finding Maximum on an Array Processor with a Global BusIEEE Transactions on Computers, 1984
- Binary Trees and Parallel Scheduling AlgorithmsIEEE Transactions on Computers, 1983
- A Computation Model of Parallel Solution of Linear EquationsIEEE Transactions on Computers, 1980
- Processor Interconnection StrategiesIEEE Transactions on Computers, 1980
- A parallel algorithm for constructing minimum spanning treesJournal of Algorithms, 1980
- Generalized Connection Networks for Parallel Processor IntercommunicationIEEE Transactions on Computers, 1978
- Optimal Sorting Algorithms for Parallel ComputersIEEE Transactions on Computers, 1978