Abstract
We present a simple deterministic O(n log2 n)-time divide-and-conquer algorithm for finding minimum cuts in planar graphs. This can be compared to a randomized algorithm for general graphs by Karger that runs in time O(m log3 n) and also a deterministic algorithm for general graphs by Nagamochi and Ibaraki that runs in time O(mn + n2 log n). We use shortest paths in the dual graphs to partition the problem, and use the relationship between minimum cuts in primal graphs and shortest paths in dual graphs to find minimum cuts that cross the partitions efficiently.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Pages | 821-822 |
| Number of pages | 2 |
| Volume | 15 |
| Publication status | Published - 2004 |
| MoE publication type | A4 Article in a conference publication |
| Event | ACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States Duration: 11 Jan 2004 → 13 Jan 2004 Conference number: 15 |
Conference
| Conference | ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Country/Territory | United States |
| City | New Orleans |
| Period | 11/01/2004 → 13/01/2004 |