Hierarchical Time-Dependent Oracles

Authors Spyros Kontogiannis, Dorothea Wagner, Christos Zaroliagis



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.47.pdf
  • Filesize: 0.67 MB
  • 13 pages

Document Identifiers

Author Details

Spyros Kontogiannis
Dorothea Wagner
Christos Zaroliagis

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

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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail