MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Shortest paths in digraphs of small treewidth sequential algorithms

Chaudhuri, Shiva and Zaroliagis, Christos D.

August 1995, 17 pages.

Status: available - back from printing

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.

  • Attachement: (87 KBytes); MPI-I-95-1-020.pdf (208 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  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},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-95-1-020},
  MONTH = {August},
  YEAR = {1995},
  ISSN = {0946-011X},