Previous Issues
Volume :25 Issue : 1 1998
Add To Cart
Download
Algorithms for shortest-paths and some related problems on a tree-structured parallel computer
Auther : PRANAY CHAUDHURI
Department of Electrical and Computer Engineering, Kuwait University, P.O. Box: 5969, Safat, 13060, Kuwait University [Fax: +965 483 0992;
Email: pranay@eng.kuniv.edu.
ABSTRACT
This paper presents parallel algorithms for the single-source shortest paths, all-paris shortest paths, analysis of activity networks, and graph-centers problems on a tree-structured computer. Assuming that all the graphs and networks under investigation consist of n nodes, the single-source shortest paths and the activity networks problems achieve a time bound of O(n2/k+n log k), whereas the all-paris shortest paths and the graph-centers problems achieve a time bound of O(n3/k+n2 log k), all with k(1£ n) processors. It is shown that, for k £ n/log n, the cost of each of these algorithms is identical to the time complexity of the corresponding best known sequential algorithms