Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
复制标题
O(n loglogn) 时间内平面图中的最小割和最短循环
DOI：
10.1007/978-3-642-23719-5_14
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
P. Sankowski
中科院分区：
文献类型：
--
作者：
Jakub Lacki;P. Sankowski
我们提出了一个确定性的O（nlog log n）时间算法寻找平面图中的最短圈和最小割。该算法将Italiano等人在STOC'11中的已知最快算法改进了log n倍。这种加速是通过使用密集距离图结合分治方法获得的。扩展这种方法，我们能够显示一个O（n5/6 log 5/2 n）时间的动态算法。
We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorithm by Italiano et al. in STOC'11 by a factor of log n. This speedup is obtained through the use of dense distance graphs combined with a divide-and-conquer approach. Extending this approach we are able to show an O(n5/6 log5/2 n) time dynamic algorithm al well.