Efficient parallel shortest-paths in digraphs with a separator decomposition

We consider(1) shortest-paths and reachability problems on directed graphs with real-valued edge weights. For sparser graphs, the known NG algorithms for these problems perform much more work than their sequential counterparts. In this paper we present efficient parallel algorithms for families of graphs, where a separator decomposition either is provided with the input or is easily obtainable. (A separator is a subset of the vertices that its removal splits the graph into connected components, such that the number of vertices in each component is at most a fixed fraction of the number of vertices in the graph. A separator decomposition is a recursive decomposition of the graph using separators.) Let G = (V, E), where n = \V\, be a weighted directed graph with a k(mu)-separator decomposition (where subgraphs with k vertices have separators of size O(k(mu))). We present an NG algorithm that computes shortest-paths from s sources to all other vertices using (O) over tilde(n(3 mu) + s(n + n(2 mu))) work. A sequential version of our algorithm improves over previously known time bounds as well. Reachability from s sources can be computed using (O) over tilde(M(n(mu)) + s(n + n(2 mu))) work, where M(r) = o(r(2.37)) is the best known work bound for r x r matrix multiplication. The algorithm is based on augmenting G with a set of (O) over tilde(n(2 mu)) edges such that in the augmented graph, all distances can be obtained by paths of size O(log n). The above bounds, with mu = 0.5, are applicable to planar graphs, since a k(0.5)-separator decomposition can be computed within these bounds. We obtain further improvements for graphs with planar embeddings where all vertices lie on a small number of faces. (C) 1996 Academic Press, Inc.