Anzeige
Erschienen in:
2001 | OriginalPaper | Buchkapitel
All-Pairs Shortest Paths Computation in the BSP Model
verfasst von : Alexandre Tiskin
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.