Faster shortest paths in dense distance graphs, with applications


          

刊名：Theoretical computer science
作者：Mozes, Shay（IDC Herzliya, Herzliyya, Israel）
Nussbaum, Yahav（Univ Haifa, Haifa, Israel）
Weimann, Oren（Univ Haifa, Haifa, Israel）
刊号：738LB004
ISSN：0304-3975
出版年：2018
年卷期：2018, vol.711
页码：11-35
总页数：25
分类号：TP3
关键词：Planar graphs；Shortest paths；Recursive r-divisions；Dynamic range minimum queries；Monge heaps
参考中译：
语种：eng
文摘：We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense distance graph (DDG). A DDG is defined for a decomposition of a planar graph G into regions of at most r vertices each, for some parameter r < n. The vertex set of the DDG is the set of Theta(nr(-1/2)) vertices of G that belong to more than one region (boundary vertices). The DDG has 8(n) arcs, such that distances in the DDG are equal to the distances in G. Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG (nicknamed FR-Dijkstra) runs in O(n log(n)r(-1/2) logr) time, and is a key component in many state-of-the-art planar graph algorithms for shortest paths, minimum cuts, and maximum flows. By combining these two techniques we remove the logn dependency in the running time of the shortest-path algorithm at the price of an additional logr factor, making it O(nr(-1/2) log(2) r).



©2016机械工业出版社（机械工业信息研究院） 京ICP备05055788号-35