Shortest paths in digraphs of small treewidth. I: Sequential algorithms (Q1578402)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Shortest paths in digraphs of small treewidth. I: Sequential algorithms |
scientific article |
Statements
Shortest paths in digraphs of small treewidth. I: Sequential algorithms (English)
0 references
17 May 2001
0 references
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.
0 references
shortest path
0 references
treewidth
0 references
partial \(k\)-trees
0 references