# Item

ITEM ACTIONSEXPORT

Released

Journal Article

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

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### 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: https://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.