An improved parallel algorithm that computes the BFS numbering of a directed graph
type: Item
instance of: scholarly article
title: An improved parallel algorithm that computes the BFS numbering of a directed graph
zbMATH Open document ID: 0658.68081
DOI: 10.1016/0020-0190(88)90164-0
author: Hillel Gazit
author: Gary L. Miller
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4076649
zbMATH Keywords: exclusive-read exclusive-write parallel random access machine
zbMATH Keywords: fast matrix multiplication
zbMATH Keywords: parallel algorithm
zbMATH Keywords: breadth-first search
zbMATH Keywords: PRAM
zbMATH Keywords: concurrent-read concurrent-write
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90164-0
OpenAlex ID: W2088570605
cites work: Q4773298
cites work: How to multiply matrices faster
cites work: Gaussian elimination is not optimal
description: scientific article; zbMATH DE number 4076649