# MPI-I-95-1-021

## Shortest paths in digraphs of small treewidth part II: optimal parallel algirithms

### Chaudhuri, Shiva and Zaroliagis, Christos D.

**MPI-I-95-1-021**. August** **1995, 20 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

We consider the problem of preprocessing an $n$-vertex digraph with

real edge weights so that subsequent queries for the shortest path or distance

between any two vertices can be efficiently answered.

We give parallel algorithms for the EREW PRAM model of computation

that depend on the {\em treewidth} of

the input graph. When the treewidth is a constant, our algorithms

can answer distance queries in $O(\alpha(n))$ time using a single

processor, after a preprocessing of $O(\log^2n)$ time and $O(n)$ work,

where $\alpha(n)$ is the inverse of Ackermann's function.

The class of constant treewidth graphs

contains outerplanar graphs and series-parallel graphs, among

others. To the best of our knowledge, these

are the first parallel algorithms which achieve these bounds

for any class of 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)$ time

using $O(n^\beta)$ work, for any constant $0 < \beta < 1$.

Moreover, we give an algorithm of independent interest:

computing a shortest path tree, or finding a negative cycle in

$O(\log^2 n)$ time using $O(n)$ work.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-95-1-021.pdf | 97 KBytes; 236 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-021

**BibTeX**
`@TECHREPORT{``ChaudhuriZaroliagis95b``,`

` AUTHOR = {Chaudhuri, Shiva and Zaroliagis, Christos D.},`

` TITLE = {Shortest paths in digraphs of small treewidth part II: optimal parallel algirithms},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-95-1-021},`

` MONTH = {August},`

` YEAR = {1995},`

` ISSN = {0946-011X},`

`}`