Kuwait-University-Journal-of-Law-header
Search
Kuwait Journal of Science

Previous Issues

Advance Search
Year : From To Vol
Issue Discipline:
Author

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

Kuwait Journal of Science
Journal of Law

You are Visitor No.

55210

Journal of Law
Journal of Law
Tell your friendsJournal of Law
Journal of Law

Last Updated

Jun 19, 2012

Journal of Law
Journal of Law
Journal of Law

Please enter your email Here to receive our news

Journal of Law