電機資訊學院: 資訊工程學研究所指導教授: 呂學一梁閎鈞Liang, Hung-ChunHung-ChunLiang2017-03-032018-07-052017-03-032018-07-052015http://ntur.lib.ntu.edu.tw//handle/246246/275551Let 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(n log3 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(n log3 n)-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in O(n log n log log n) time via a divide-and-conquer algorithm that finds a shortest non-degenerate cycle. The kernel of our result is an O(n log log n)-time algorithm for computing shortest noncrossing 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.388842 bytesapplication/pdf論文公開時間: 2015/8/21論文使用權限: 同意有償授權(權利金給回饋學校)演算法平面圖最小切割最短路徑algorithmplanar graphminimum cutshortest paththesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/275551/1/ntu-104-R01922034-1.pdf