Simple Parallel Algorithms for the All-pair Shortest Path Query Problem on Interval and Circular-arc Graphs

摘要

In this paper, we consider the problem for the all-pair shortest path queries on interval and circular-arc graphs. Instead of using the sophisticated technique, we propose simple parallel algorithms using only the parallel prefix and suffix computations and the Euler tour technique. Our preprocessing algorithms run in O(log n) time using O(n/log n) processors. Using the data structure constructed by our preprocessing algorithms, a query of the length of a shortest path between any two vertices can be answered in constant time by using a single processor. Our algorithms are on the EREW PRAM model.