A deterministic near-linear time algorithm for finding minimum cuts in planar graphs

Parinya Chalermsook*, Jittat Fakcharoenphol, Danupon Nanongkai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

23 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages821-822
Number of pages2
Volume15
Publication statusPublished - 2004
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States
Duration: 11 Jan 200413 Jan 2004
Conference number: 15

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans
Period11/01/200413/01/2004

Fingerprint Dive into the research topics of 'A deterministic near-linear time algorithm for finding minimum cuts in planar graphs'. Together they form a unique fingerprint.

Cite this