Standard

All-pairs shortest paths computation in the BSP model. / Tiskin, Alexandre.

Automata, Languages and Programming (ICALP 2001). 2001. p. 178-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2076).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Tiskin, A 2001, All-pairs shortest paths computation in the BSP model. in Automata, Languages and Programming (ICALP 2001). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2076, pp. 178-189. https://doi.org/10.1007/3-540-48224-5_15

APA

Tiskin, A. (2001). All-pairs shortest paths computation in the BSP model. In Automata, Languages and Programming (ICALP 2001) (pp. 178-189). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2076). https://doi.org/10.1007/3-540-48224-5_15

Vancouver

Tiskin A. All-pairs shortest paths computation in the BSP model. In Automata, Languages and Programming (ICALP 2001). 2001. p. 178-189. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-48224-5_15

Author

Tiskin, Alexandre. / All-pairs shortest paths computation in the BSP model. Automata, Languages and Programming (ICALP 2001). 2001. pp. 178-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{d44c66cb0137428ba6e6ac2d2c6155d8,
title = "All-pairs shortest paths computation in the BSP model",
abstract = "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. {\textcopyright} 2011 Springer-Verlag Berlin Heidelberg.",
author = "Alexandre Tiskin",
year = "2001",
month = jan,
day = "1",
doi = "10.1007/3-540-48224-5_15",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "178--189",
booktitle = "Automata, Languages and Programming (ICALP 2001)",

}

RIS

TY - GEN

T1 - All-pairs shortest paths computation in the BSP model

AU - Tiskin, Alexandre

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=23044525996&partnerID=8YFLogxK

U2 - 10.1007/3-540-48224-5_15

DO - 10.1007/3-540-48224-5_15

M3 - Conference contribution

AN - SCOPUS:23044525996

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 178

EP - 189

BT - Automata, Languages and Programming (ICALP 2001)

ER -

ID: 127723519