Hierarchical Oracles for Time-Dependent Networks.
Spyros C. Kontogiannis, Dorothea Wagner, Christos Zaroliagis · arXiv (Cornell University) · 2015
We present novel oracles for networks that obey time-dependent metrics with two unique features: (i) they provably achieve subquadratic preprocessing time and space that is \emph{independent} of the metric; (ii) they provably achieve query time that is sublinear either on the network size, or on the actual \emph{Dijkstra Rank} of the query at hand.