文章基本信息

标题：Hierarchical Time-Dependent Oracles
本地全文：下载
作者：Spyros Kontogiannis ; Dorothea Wagner ; Christos Zaroliagis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：64
页码：47:1-47:13
DOI：10.4230/LIPIcs.ISAAC.2016.47
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Time-dependent shortest paths; FIFO property; Distance oracles