期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 31, 期 1, 页码 454-476出版社
SIAM PUBLICATIONS
DOI: 10.1137/16M1057152
关键词
planar graph; minimum cut; shortest cycle; girth
资金
- MOST [104-2221-E-002-044-MY3]
Let G be an n-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of G with minimum weight and (2) a cycle of G with minimum weight. The best previously known algorithm for the former problem, running in O(nlog(3)n) time, can be obtained from the algorithm of Lacki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the O(nlog(3)n)-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in O(nlognloglogn) time via a divide-and-conquer algorithm that finds a shortest non-degenerate cycle. The kernel of our result is an O(nloglogn)-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据