max planck institut
informatik

MPI-I-95-1-020

Shortest paths in digraphs of small treewidth sequential algorithms

Chaudhuri, Shiva and Zaroliagis, Christos D.

MPI-I-95-1-020. August 1995, 17 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 algorithms
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 after $O(n)$ preprocessing. This improves upon
previously known results for the same problem.
We also give a
dynamic algorithm which, after a change in an edge weight, updates the
data structure in time $O(n^\beta)$, for any constant $0 < \beta < 1$.
Furthermore, an algorithm of independent interest is given:
computing a shortest path tree, or finding a negative cycle in linear
time.
Acknowledgement:
References to related material:

MPI-I-95-1-020.pdf87 KBytes; 208 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-020
BibTeX
@TECHREPORT{ChaudhuriZaroliagis95a,
AUTHOR = {Chaudhuri, Shiva and Zaroliagis, Christos D.},
TITLE = {Shortest paths in digraphs of small treewidth sequential algorithms},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},