Parallel computing dominators on hypercube multiprocessors
Shi‐Jinn Horng · 2002
Two O(log/sup 2/ n) time algorithms are proposed for computing the dominators and constructing the dominator tree of a directed acyclic graph, G=(V, E), |V|=n, |E|=m. The parallel computation used is a practical SIMD hypercube multiprocessor with n/sup 3/ processing elements. The algorithms developed in this paper achieve the same time complexity as those developed on PRAM model (S. Pawagi, 1987), (C. Savage, 1977) but are more practical.>