An improved parallel algorithm that computes the BFS numbering of a directed graph (Q1111392)

This paper presents a parallel algorithm that computes the breadth-first search (BFS) numbering of a directed graph in \(O(\log^ 2 n)\) time using M(n) processors on the exclusive-read exclusive-write (EREW) parallel random access machine (PRAM) model, where M(n) denotes the number of processors needed to multiply two \(n\times n\) integer matrices over the ring (\({\mathbb{Z}}\), \(+\), \(\times)\) in O(log n) time. The best known bound for M(n) is \(O(n^{2.376})\) [\textit{D. Coppersmith} and \textit{S. Winograd}, Matrix-multiplication via arithmetic progression, Proc. 19th Ann. ACM Symp. Theory Comput., 1-6 (1987)]. The algorithm presented in their paper uses fewer processors than the classical algorithm for BFS that employs matrix powering over the semiring (dioid) (\({\mathbb{N}}\), min, \(+)\), using O(log n) time and \(O(n^ 3)\) processors on the concurrent-read concurrent-write (CRCW) model, or using \(O(\log^ 2 n)\) time and \(n^ 3/\log n\) processors on the EREW model.