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:Inproceedings
Entered by:
TitleDynamic Shortest Paths Containers
Bibtex cite IDRACTI-RU1-2003-60
Booktitle Electronic Notes in Theoretical Computer Science
Series Proceedings of ATMOS Workshop 2003
Year published 2003
Month February
Volume 92
Pages 65-84
Publisher Elsevier
DOI 10.1016/j.entcs.2003.12.023
Keywords geometric container; dynamic shortest path; graph layout
Using a set of geometric containers to speed up shortest path queries in a weighted graph has been proven a useful tool for dealing with large sparse graphs. Given a layout of a graph G=(V,E), we store, for each edge (u,v)set membership, variantE, the bounding box of all nodes tset membership, variantV for which a shortest u-t-path starts with (u,v). Shortest path queries can then be answered by DijkstraImage restricted to edges where the corresponding bounding box contains the target. In this paper, we present new algorithms as well as an empirical study for the dynamic case of this problem, where edge weights are subject to change and the bounding boxes have to be updated. We evaluate the quality and the time for different update strategies that guarantee correct shortest paths in an interesting application to railway information systems, using real-world data from six European countries.
Wagner, Dorothea
Willham, Thomas
Zaroliagis, Christos
fulltext.pdf (main file)
Publication ID606