Hierarchical time-dependent oracles

DOI10.4230/LIPICS.ISAAC.2016.47MaRDI QIDQ4636530zbMATH OpenOpenAlexFDO

Authors Dorothea Wagner, Spyros Kontogiannis, Christos Zaroliagis

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1502.05222

zbMATH Keywords

distance oraclesFIFO propertytime-dependent shortest paths

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: We study networks obeying emph{time-dependent} min-cost path metrics, and present novel oracles for them which emph{provably} achieve two unique features: % (i) emph{subquadratic} preprocessing time and space, emph{independent} of the metric's amount of disconcavity; % (ii) emph{sublinear} query time, in either the network size or the actual Dijkstra-Rank of the query at hand.

Recommendations

• An axiomatic approach to time-dependent shortest path oracles
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Engineering oracles for time-dependent road networks

Cited in

(6)

• Tighter constant-factor time hierarchies
• An axiomatic approach to time-dependent shortest path oracles
• Separating the low and high hierarchies by oracles
• scientific article; zbMATH DE number 6712240 (Why is no real title available?)
• Engineering oracles for time-dependent road networks
• Improved oracles for time-dependent road networks

This page was built for publication: Hierarchical time-dependent oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636530)