Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
复制标题
具有改进的查询时空权衡的平面图的近似距离预言
DOI：
10.1137/1.9781611974331.ch26
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Christian Wulff
中科院分区：
文献类型：
--
作者：
Christian Wulff
我们考虑了边加权n顶点无向平面图的近似距离预言。给定固定的e > 0。我们提出了一个(1 + e)-近似距离的oracle，其空间为O(n(log log n)2)，查询时间为O((log log n)3)。这将Thorup （FOCS 2001， J. ACM 2004）和Klein （SODA 2002）的预言机的查询时间和空间的最佳产品从O（n log n）提高到O（n(log log n)5）。
We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed e > 0. we present a (1 + e)-approximate distance oracle with O(n(log log n)2) space and O((log log n)3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(n log n) to O(n(log log n)5).