hide
Free keywords:
-
Abstract:
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 treewidth of the input graph. When the treewidth is a constant, our
algorithms can answer distance queries in O(α(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β) , for any
constant 0 < β < 1 . Furthermore, an algorithm of independent interest is
given: computing a shortest path tree, or finding a negative cycle in linear
time.
