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:
TitleImproved Algorithms for Dynamic Shortest Paths
Bibtex cite IDRACTI-RU1-2000-14
Journal Algorithmica
Year published 2000
Volume 28
Number 4
Pages 367-389
Keywords Shortest path,Dynamic algorithm,Planar digraph,Outerplanar digraph
We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n-vertex digraphs of genus O.n1"/ for any " > 0.
Djidjev, H.
Pantziou, Grammati
Zaroliagis, Christos
J15-algo-dsp-10043.pdf (main file)
Publication ID410