Title: Solving the All-Pair Shortest Path Query Problem on Interval and Circular-Arc Graphs

Danny Z. Chen
Department of Computer Science and Engineering 
University of Notre Dame 
Notre Dame, IN 46556 
chen@cse.nd.edu

D. T. Lee* 

Department of Electrical and Computer Engineering 
Northwestern University 
Evanston, IL 60208 USA
dtlee@ece.nwu.edu

* Supported in part by the National Science Foundation  under 
  Grants CCR-8901815 and CCR-9309743.

R. Sridhar
School of Computer Science
University of Oklahoma
Norman, OK 73019
sridhar@giants.ecn.uoknor.edu

Chandra N. Sekharan
Department of Mathematical and Computer Sciences
Loyola University of Chicago
Chicago, IL 60626
chandra@math.luc.edu

Abstract:

In this paper, we study the following all-pair shortest path query problem:
Given the interval model of an unweighted interval graph of $n$ vertices,
build a data structure such that each query on the shortest path (or its length)
between any pair of vertices of the graph can be processed efficiently (both 
sequentially and in parallel).  We show that, after sorting the input intervals 
by their endpoints, a data structure can be constructed sequentially in $O(n)$ time 
and $O(n)$ space; using this data structure, each query on the length of
the shortest path between any two intervals can be answered in $O(1)$ time, and 
each query on the actual shortest path can be answered in $O(k)$ time, where $k$ 
is the number 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 extended to solving the all-pair 
shortest path query problem on circular-arc graphs, both sequentially and in parallel,
in the same complexity bounds.  As an immediate consequence of our results, we improve 
by a factor of $n$ the space complexity of the previously best known sequential
all-pair shortest path algorithm for unweighted interval graphs.

Networks, (32,4): 249-257, Dec. 1998.