Shortest paths in digraphs of small treewidth. I: Sequential algorithms (Q1578402)

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.