https://scholars.lib.ntu.edu.tw/handle/123456789/488594
標題: | Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths | 作者: | Liang, H.-C. HSUEH-I LU |
關鍵字: | Girth; Minimum cut; Planar graph; Shortest cycle | 公開日期: | 2017 | 卷: | 31 | 期: | 1 | 起(迄)頁: | 454-476 | 來源出版物: | SIAM Journal on Discrete Mathematics | 摘要: | 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(n log3 n) time, can be obtained from the algorithm of Laçki, 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 nondegenerate cycle. The kernel of our result is an O(n log log n)-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. © 2017 Society for Industrial and Applied Mathematics. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85018691610&doi=10.1137%2f16M1057152&partnerID=40&md5=6582f4255bf3c69601bc065db978b91c | DOI: | 10.1137/16M1057152 | SDG/關鍵字: | Directed graphs; Graphic methods; Problem solving; Divide-and-conquer algorithm; Girth; Minimum cut; Minimum weight; Nondegenerate; Planar graph; Shortest cycle; Time algorithms; Graph theory |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。