Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
复制标题
平面、有界格属和次自由图的线性空间近似距离预言
DOI：
10.1007/978-3-642-22006-7_12
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Christian Sommer
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;P. Klein;Christian Sommer
图的（1+e）-近似距离预言机是一种支持近似点到点最短路径距离查询的数据结构。距离预言机构造的最相关的度量是：空间、查询时间和预处理时间。
平面图（Thorup，JACM'04）和随后的小排除图（Abraham和Gavoille，PODC'06）都有强距离预言结构。然而，这些需要Ω（e-1 nlgn）空间的n-节点图。
在本文中，对于平面图，有界亏格图，和小排除图，我们给出的距离预言的结构，只需要O（n）空间。大O只隐藏了一个固定的常数，与e无关，也与被排除子式的亏格或大小无关。我们的距离预言机的预处理时间也比以前已知的构造更快。对于平面图，预处理时间为O（nlg 2n）.然而，我们的构造具有较慢的查询时间。对于平面图，查询时间为O（e-2lg 2n）。
对于我们所有的线性空间结果，我们实际上可以保证，对于任何δ > 0，所需的空间仅是表示图本身所需空间的1 + δ倍。
A (1+e)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time.
There are strong distance-oracle constructions known for planar graphs (Thorup, JACM'04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC'06). However, these require Ω(e-1n lg n) space for n-node graphs.
In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of e and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(nlg2 n). However, our constructions have slower query times. For planar graphs, the query time is O(e-2 lg2 n).
For all our linear-space results, we can in fact ensure, for any δ > 0, that the space required is only 1 + δ times the space required just to represent the graph itself.