Shortest paths in digraphs of small treewidth. I: Sequential algorithms
An algorithm is developed for answering shortest path queries on graphs with constant treewidth (i.e., partial \(k\)-trees for constant \(k\)), by employing an amount of preprocessing which is linear in the size of the graph. Distance queries can be answered in time proportional to the inverse of the Ackermann function evaluated at the number \(n\) of vertices. A sublinear algorithm is given for updating edge weights dynamically.
scientific article; zbMATH DE number 1496842