ALGORITHMS FOR SHORTEST-PATHS AND SOME RELATED PROBLEMS ON A TREE-STRUCTURED PARALLEL COMPUTER

This paper presents parallel algorithms for the single-source shortest paths, all-pairs shortest paths, analysis of activity networks, and g raph-centers problems on a tree-structured computer. Assuming that all the graphs and networks under investigation consist of n nodes, the s ingle-source shortest paths and the activity networks problems achieve a time bound of O(n(2)/k + n log k), whereas the all-pairs shortest p aths and the graph-centers problems achieve a time bound of O(n(3)/k n(2) log k), all with k(1 < k less than or equal to n) processors. It is shown that, for k less than or equal to n/log n, the cost of each of these algorithms is identical to the time complexity of the corresp onding best known sequential algorithm.