Faster Approximate Diameter and Distance Oracles in Planar Graphs
Faster Approximate Diameter and Distance Oracles in Planar Graphs
复制标题
平面图中更快的近似直径和距离预言
DOI：
10.1007/s00453-019-00570-z
复制
发表时间：
2019
期刊：
影响因子：
1.1
通讯作者：
Skrepetos, Dimitrios
中科院分区：
文献类型：
--
作者：
Chan, Timothy M.;Skrepetos, Dimitrios
本文提出了一个计算n个顶点的无向平面图的直径的a-近似的时间算法。这是对Weimann和Yuster的算法（ACM Trans Algorithms 12（1）：12，2016）的改进。首先，我们通过调整和专门化Cabello最近的基于Voronoi图的技术（Cabello，在：第28届ACM-SIAM离散算法研讨会（SODA）会议记录，2017）来消除对的指数依赖性。其次，通过选择较好的误差参数序列，去掉了两个对数因子。此外，使用类似的技术，我们获得了Gu和Xu的近似距离预言的变体（Gu和Xu，在：Proceedings of the 26 th International Symposium on Algorithms and Computation（ISAAC），2015），在预处理时间和空间以及查询时间上具有多项式依赖性。
We present an-time algorithm that computes a-approximation of thediameterof a non-negatively-weighted, undirected planar graph ofnvertices. This is an improvement over the algorithm of Weimann and Yuster (ACM Trans Algorithms 12(1):12, 2016) oftime in two regards. First we eliminate the exponential dependency onby adapting and specializing Cabello’s recent Voronoi-diagram-based technique (Cabello, in: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017) for approximation purposes. Second we shave off two logarithmic factors by choosing a better sequence of error parameters in the recursion. Moreover, using similar techniques we obtain a variant of Gu and Xu’s-approximate distance oracle (Gu and Xu, in: Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), 2015) with polynomial dependency onin the preprocessing time and space andquery time.
登录
查看更多内容
改进了图形的稀疏覆盖，不包括固定次要的
DOI：
10.1145/1281100.1281112
发表时间：
2007
期刊：
ArXiv
影响因子：
--
作者：
C. Busch;Ryan LaFortune;Srikanta Tirthapura
通讯作者：
Srikanta Tirthapura
更快地近似图中的距离
影响因子：
1.1
作者：
P. Berman;S. Kasiviswanathan
通讯作者：
S. Kasiviswanathan
DOI：
10.1016/0925-7721(93)90033-3
发表时间：
1993-08-01
影响因子：
0.6
作者：
KLEIN, R;MEHLHORN, K;MEISER, S
通讯作者：
MEISER, S
平面、有界格属和次自由图的线性空间近似距离预言
DOI：
10.1007/978-3-642-22006-7_12
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
K. Kawarabayashi;P. Klein;Christian Sommer
通讯作者：
Christian Sommer
具有改进的查询时空权衡的平面图的近似距离预言
DOI：
10.1137/1.9781611974331.ch26
发表时间：
2016
期刊：
ArXiv
影响因子：
--
作者：
Christian Wulff
通讯作者：
Christian Wulff