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

Citation
S. Chaudhuri et Cd. Zaroliagis, Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms, ALGORITHMIC, 27(3-4), 2000, pp. 212-226
Citations number
17
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
01784617 → ACNP
Volume
27
Issue
3-4
Year of publication
2000
Pages
212 - 226
Database
ISI
SICI code
0178-4617(200007/08)27:3-4<212:SPIDOS>2.0.ZU;2-Z
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 betwe en any two vertices can be efficiently answered. We give algorithms that de pend on the treewidth of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in O(alpha(n)) time after O(n) preprocessing. This improves upon previously known results for the same pro blem. We also give a dyna the data structure in time O(n(beta)), for any co nstant 0 < beta < 1. Furthermore, an algorithm of independent interest is g iven: computing a shortest path tree, or finding a negative cycle in linear time.