An optimal parallel processor bound in strong orientation of an undirected graph (Q1062459)

Recently, \textit{M. J. Atallah} [ibid. 18, 37-39 (1984; Zbl 0532.68065)] presented an algorithm for assigning directions to the edges of a connected, bridgeless undirected graph so that the resulting directed graph is strong in the sense that there is a directed path from u to v for every two vertices u, v in it. Atallah indicated that a direct implementation of that algorithm takes \(O(\log^ 2n)\) time with \(O(n^ 4)\) processors on the PRAM - a SIMD shared memory model allowing read but not write conflicts - where n is the size of the vertex set. He then proceeded to give an implementation which takes \(O(\log^ 2n)\) time with \(O(n^ 3)\) processors. Our aim is to present an implementation which takes \(O(\log^ 2n)\) time with \(n\lceil n/\log^ 2n\rceil\) processors on the PRAM. This result reduces the number of processors used by a factor of n \(\log^ 2n\) and is optimal for dense graphs.