research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleShortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms
Bibtex cite IDRACTI-RU1-2000-16
Journal Algorithmica
Year published 2000
Volume 27
Number 3
Pages 212-226
Keywords Shortest path,Graph theory,Treewidth,Dynamic algorithm
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.
Shiva, Chaudhuri
Zaroliagis, Christos
J13-algo-spi-10016.pdf (main file)
Publication ID412