Oracles for bounded-length shortest paths in planar graphs
Oracles for bounded-length shortest paths in planar graphs
复制标题
平面图中有限长度最短路径的预言机
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Maciej Kurowski
中科院分区：
文献类型：
--
作者：
Lukasz Kowalik;Maciej Kurowski
我们提出了一种新的方法来回答平面图中的最短路径查询。对于任意固定常数k和给定的无权平面图G =（V，E），可以在O（|V|一个数据结构，它允许在O（1）时间内检查两个给定的顶点是否在G中的距离最多为k，如果是，则返回它们之间的最短路径。图G可以是无向的，也可以是有向的，我们的数据结构可以在完全动态的环境下工作。在删除一条边或一个顶点后，它可以在O（1）时间内更新，而在边插入后更新需要多对数摊销时间。除了删除元素，还可以禁用一段时间。我们的结果可以很容易地推广到其他广泛的图类--例如，我们可以采取任何小闭图族。
We present a new approach for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G = (V, E), one can build in O(|V|) time a data structure, which allows to check in O(1) time whether two given vertices are at distance at most k in G and if so a shortest path between them is returned. Graph G can be undirected as well as directed.Our data structure works in fully dynamic environment. It can be updated in O(1) time after removing an edge or a vertex while updating after an edge insertion takes polylogarithmic amortized time. Besides deleting elements one can also disable ones for some time. It is motivated by a practical situation where nodes or links of a network may be temporarily out of service.Our results can be easily generalized to other wide classes of graphs---for instance we can take any minor-closed family of graphs.