Back to Search
Start Over
MINIMUM CUTS AND SHORTEST CYCLES IN DIRECTED PLANAR GRAPHS VIA NONCROSSING SHORTEST PATHS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2017, Vol. 31 Issue 1, p454-476. 23p. - Publication Year :
- 2017
-
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³ n) time, can be obtained from the algorithm of Łącki, 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³ 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 divideand-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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 31
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 122891397
- Full Text :
- https://doi.org/10.1137/16M1057152