SHORTEST PATHS IN DIGRAPHS OF SMALL TREEWIDTH - PART II - OPTIMAL PARALLEL ALGORITHMS

We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or dist ance between any two vertices can be efficiently answered. We give par allel algorithms for the EREW PRAM model of computation that depend on the treewidth of the input graph. When the treewidth is a constant, o ur algorithms can answer distance queries in O(alpha(n)) time using a single processor, after a preprocessing of O(log(2)n) time and O(n) wo rk, where alpha(n) is the inverse of Ackermann's function. The class o f constant treewidth graphs contains outerplanar graphs and series-par allel graphs, among others. To the best of our knowledge, these are th e first parallel algorithms which achieve these bounds for any class o f graphs except trees. We also give a dynamic algorithm which, after a change in an edge weight, updates our data structures in O(log n) tim e using O(n(beta)) work, for any constant 0<beta<1 Moreover, we give a n algorithm of independent interest: computing a shortest path tree, o r finding a negative cycle in O(log(2)n) time using O(n) work. (C) 199 8-Elsevier Science B.V. All rights reserved.