DOI

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose a new p-processor BSP algorithm for the all-pairs shortest paths problem in a weighted directed dense graph. In contrast with the general algebraic path algorithm, which performs O(p1/2) to O(p2/3) global synchronisation steps, our new algorithm only requires O(log p) synchronisation steps. © 2011 Springer-Verlag Berlin Heidelberg.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming (ICALP 2001)
Pages178-189
Number of pages12
DOIs
StatePublished - 1 Jan 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
Volume2076
ISSN (Print)0302-9743

ID: 127723519