Solving tree problems on a mesh-connected processor array
- 1 January 1985
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper we present techniques that result in O(√n) time algorithms for computing many properties and functions of an n-node forest stored in an √n × √n mesh of processors. Our algorithms include computing simple properties like the depth, the height, the number of descendents, the preorder (resp. postorder, inorder) number of every node, and a solution to the more complex problem of computing the Minimax value of a game tree. Our algorithms are asymptotically optimal since any nontrivial computation will require Ω (√n) time on the mesh. All of our algorithms generalize to higher dimensional meshes.Keywords
This publication has 9 references indexed in Scilit:
- On efficient parallel strong orientationInformation Processing Letters, 1985
- Finding Euler tours in parallelJournal of Computer and System Sciences, 1984
- Efficient Parallel Algorithms for a Class of Graph Theoretic ProblemsSIAM Journal on Computing, 1984
- Graph Problems on a Mesh-Connected Processor ArrayJournal of the ACM, 1984
- Parallel strong orientation of an undirected graphInformation Processing Letters, 1984
- Optimal BPC Permutations on a Cube Connected SIMD ComputerIEEE Transactions on Computers, 1982
- Finding Connected Components and Connected Ones on a Mesh-Connected Parallel ComputerSIAM Journal on Computing, 1980
- Computing connected components on parallel computersCommunications of the ACM, 1979
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977