# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Shortest paths in digraphs of small treewidth. Part I, Sequential algorithms

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Chaudhuri, S., & Zaroliagis, C. (2000). Shortest paths in digraphs of small treewidth.
Part I, Sequential algorithms.* Algorithmica,* *27*(3/4),
212-226.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-33FD-6

##### 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.