Scalability of parallel algorithms for the all-pairs shortest-path problem

Vipin Kumar, Vineet Singh

Research output: Contribution to journalArticlepeer-review

47 Scopus citations


This paper uses the isoefficiency metric to analyze the scalability of several parallel algorithms for finding shortest paths between all pairs of nodes in a densely connected graph. Parallel algorithms analyzed in this paper either have been previously presented elsewhere or are small variations of them. Scalability is analyzed with respect to mesh, hypercube, and shared-memory architectures. We demonstrate that isoefficiency functions are a compact and useful predictor of performance. In fact, previous comparative predictions of some of the algorithms based on experimental results are shown to be incorrect whereas isoefficiency functions predict correctly. We find the classic trade-offs of hardware cost vs time and memory vs time to be represented here as trade-offs of hardware cost vs scalability and memory vs scalability.

Original languageEnglish (US)
Pages (from-to)124-138
Number of pages15
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - Oct 1991

Bibliographical note

Funding Information:
* This work was partially supported by Army Research Office Grant 28408-MA-SD1 to the University of Minnesota and by the Army High Performance Computing Research Center at the University of Minnesota. A short version of this paper appeared in the Proc. 1990 International Conference on Parallel Processing.


Dive into the research topics of 'Scalability of parallel algorithms for the all-pairs shortest-path problem'. Together they form a unique fingerprint.

Cite this