LIPIcs.ISAAC.2016.47.pdf
- Filesize: 0.67 MB
- 13 pages
Document
Hierarchical Time-Dependent Oracles
Authors
-
Part of:
Volume:
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-12-07
Cite AsGet BibTex
Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis. Hierarchical Time-Dependent Oracles. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.47
https://doi.org/10.4230/LIPIcs.ISAAC.2016.47
Abstract
We study networks obeying time-dependent min-cost path metrics, and present novel oracles for them which provably achieve two unique features: (i) subquadratic preprocessing time and space, independent of the metric’s amount of disconcavity; (ii) sublinear query time, in either the network size or the actual Dijkstra-Rank of the query at hand.
Keywords
- Time-dependent shortest paths
- FIFO property
- Distance oracles
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads