de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

#### Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44233

Chaudhuri,  Shiva
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45787

Zaroliagis,  Christos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Chaudhuri, S., & Zaroliagis, C. (1998). Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms. Theoretical Computer Science, 203(2), 205-223.

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 &lt; \beta &lt; 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.