Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
复制标题
通过禁止设置的距离标签实现平面图的完全动态近似距离预言
DOI：
10.1145/2213977.2214084
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
C. Gavoille
中科院分区：
文献类型：
--
作者：
Ittai Abraham;S. Chechik;C. Gavoille
本文考虑平面图的完全动态（1 + ε）距离预言机和（1 + ε）禁止集标记方案。对于给定的具有从[1, M]中抽取的边权的n个顶点的平面图G以及参数ε > 0，我们的禁止集标记方案使用长度为λ = O(ε⁻¹ log²n log(nM) • maxlogn)的标记。给定两个顶点s和t以及故障顶点/边的集合F的标记，我们的方案在O(|F|²λ)时间内以伸展因子（1 + ε）近似G \ F中s和t之间的距离。
然后我们提出一种将（1 + ε）禁止集标记方案转换为完全动态（1 + ε）距离预言机的通用方法。我们的完全动态（1 + ε）距离预言机的大小为O(n log{n} • maxlogn)，并且具有~O(n¹/²)的查询和更新时间，查询和更新时间都是最坏情况。这改进了先前已知的平面图的最佳（1 + ε）动态距离预言机，其最坏情况查询时间为~O(n²/³)，平摊更新时间为~O(n²/³)。
我们的（1 + ε）禁止集标记方案也可以扩展为具有伸展因子（1 + ε）的禁止集标记路由方案。
This paper considers fully dynamic (1+ε) distance oracles and (1+ε) forbidden-set labeling schemes for planar graphs. For a given n-vertex planar graph G with edge weights drawn from [1,M] and parameter ε>0, our forbidden-set labeling scheme uses labels of length λ = O(ε-1 log2n log(nM) • maxlogn). Given the labels of two vertices s and t and of a set F of faulty vertices/edges, our scheme approximates the distance between s and t in G \ F with stretch (1+ε), in O(|F|2 λ) time.
We then present a general method to transform (1+ε) forbidden-set labeling schemas into a fully dynamic (1+ε) distance oracle. Our fully dynamic (1+ε) distance oracle is of size O(n log{n} • maxlogn) and has ~O(n1/2) query and update time, both the query and the update time are worst case. This improves on the best previously known (1+ε) dynamic distance oracle for planar graphs, which has worst case query time ~O(n2/3) and amortized update time of ~O(n2/3).
Our (1+ε) forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch (1+ε).