论文标题
真正的次级次级精确距离甲骨文具有恒定查询时间的平面图
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs
论文作者
论文摘要
鉴于带有$ n $顶点的未方向，未加权的平面图$ g $，我们提供了一个真正的次级尺寸距离甲骨文，用于在恒定时间内报告任何一对$ g $的顶点之间的确切最短路径距离。对于任何$ \ varepsilon> 0 $，我们的距离Oracle占用$ O（n^{5/3+\ varepsilon}）$ space，并且能够针对任何一对$ g $的最短路径距离查询在worst-case time $ o（\ log（\ log log（1/\ varepsilon）中）。以前没有真正的次级尺寸距离距离距离恒定查询时间可以回答确切的全对最短路径的距离查询。
Given an undirected, unweighted planar graph $G$ with $n$ vertices, we present a truly subquadratic size distance oracle for reporting exact shortest-path distances between any pair of vertices of $G$ in constant time. For any $\varepsilon > 0$, our distance oracle takes up $O(n^{5/3+\varepsilon})$ space and is capable of answering shortest-path distance queries exactly for any pair of vertices of $G$ in worst-case time $O(\log (1/\varepsilon))$. Previously no truly sub-quadratic size distance oracles with constant query time for answering exact all-pairs shortest paths distance queries existed.
