SOLVING THE ALL-PAIR SHORTEST-PATH QUERY PROBLEM ON INTERVAL AND CIRCULAR-ARC GRAPHS

In this paper, we study the following all-pair shortest path query pro blem: Given the interval model of an unweighted interval graph of n ve rtices, build a data structure such that each query on the shortest pa th (or its length) between any pair of vertices of the graph can be pr ocessed efficiently (both sequentially and in parallel). We show that, after sorting the input intervals by their endpoints, a data structur e can be constructed sequentially in O(n) time and O(n) space; using t his data structure, each query on the length of the shortest path betw een any two intervals can be answered in O(l)time, and each query on t he actual shortest path can be answered in O(k) time, where k is the n umber of intervals on that path. Furthermore, this data structure can be constructed optimally in parallel, in O(log n) time using O(n/log n ) CREW PRAM processors; each query on the actual shortest path can be answered in O(1) time using k processors. Our techniques can be extend ed to solving the all-pair shortest path query problem on circular-are graphs, both sequentially and in parallel, in the same complexity bou nds. As an immediate consequence of our results, we improve by a facto r of n the space complexity of the previously best-known sequential al l-pair shortest path algorithm for unweighted interval graphs. (C) 199 8 John Wiley & Sons, Inc. Networks 31: 249-258, 1998.