Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 517688.0, MPI für Informatik / Algorithms and Complexity Group
Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms
Authors:
Language:English
Date of Publication (YYYY-MM-DD):1998
Title of Journal:Theoretical Computer Science
Volume:203
Issue / Number:2
Start Page:205
End Page:223
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-0FAB3FA4CE2F4A9CC125648400504A55-...
ISSN:0304-3975
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.