AbstractA cost optimal parallel algorithm is presented to find the all-pairs shortest paths on an unweighted interval graph which takes O(n/p + log n) time on an EREW PRAM, where np and n represent respectively the number of processors and the number of vertices of the graph.
Categories and Subject Descriptors: E.1 [Data Structures]; F.2 [Analysis of Algorithms and Problem Complexity]; G.2.2 [Discrete Mathematics]: Graph Theory; I.1.2 [Algebraic Manipulation]: Algorithms
Additional Key Words and Phrases: design and analysis of algorithms, parallel algorithm, interval graph, all-pairs shortest paths, EREW PRAM
Selected references
- Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, and Robert E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, 37(2):213-223, April 1990.
- Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255-262, April 1997.
- Calvin C.-Y. Chen and Sajal K. Das. Breadth-first traversal of trees and integer sorting in parallel. Information Processing Letters, 41(1):39-49, 21 January 1992.
- Calvin C.-Y. Chen, Sajal K. Das, and Selim G. Akl. A unified approach to parallel depth-first traversals of general trees. Information Processing Letters, 38(1):49-55, 12 April 1991.
- Eliezer Dekel, David Nassimi, and Sartaj Sahni. Parallel matrix and graph algorithms. SIAM Journal on Computing, 10(4):657-675, November 1981.
- Zvi Galil and Oded Margalit. All pairs shortest distances for graphs with small integer length edges. Information and Computation, 134(2):103-139, 1 May 1997.
- Grammati E. Pantziou, Paul G. Spirakis, and Christos D. Zaroliagis. Efficient parallel algorithms for shortest paths in planar graphs. In John R. Gilbert and Rolf G. Karlsson, editors, SWAT 90, 2nd Scandinavian Workshop on Algorithm Theory, volume 447 of Lecture Notes in Computer Science, pages 288-300, Bergen, Norway, 11-14 July 1990. Springer.
- G. Ramalingam and C. Pandu Rangan. A unified approach to domination problems on interval graphs. Information Processing Letters, 27(5):271-274, 28 April 1988.
- Raimund Seidel. On the all-pairs-shortest-path problem. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 745-749, Victoria, British Columbia, Canada, 4-6 May 1992.
- Tadao Takaoka. A new upper bound on the complexity of the all pairs shortest path problem. Information Processing Letters, 43(4):195-199, 28 September 1992.