AN OPTIMAL PARALLEL ALGORITHM FOR SOLVING ALL-PAIRS SHORTEST PATHS PROBLEM ON CIRCULAR-ARC GRAPHS

Abstract. The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why short-est path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents an O(n2) time sequential algorithm and an O(n2/p + log n) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, where p and n represent respectively the number of processors and the number of vertices of the circular-arc graph