{"id":"arxiv:1703.07964","kind":"preprint","title":"Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths","authors":["Hung-Chun Liang","Hsueh-I Lu"],"author_count":2,"year":2017,"published":"2017-03-23","venue":"SIAM Journal on Discrete Mathematics 31 (1): 454-476, 2017","cited_by":null,"doi":"10.1137/16m1057152","arxiv_id":"1703.07964","nct_id":null,"source_url":"https://arxiv.org/abs/1703.07964","archive_url":"https://space-kitty.com/papers/arxiv:1703.07964","updated":"2017-03-23","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/1703.07964","abstract":"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\\log^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(n\\log^3 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 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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}