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

Parinya Chalermsook; Jittat Fakcharoenphol; Danupon Nanongkai

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

Parinya Chalermsook^*, Jittat Fakcharoenphol, Danupon Nanongkai

^*Corresponding author for this work

Not published at Aalto University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

23 Citations (Scopus)

Abstract

We present a simple deterministic O(n log² 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 log³ n) and also a deterministic algorithm for general graphs by Nagamochi and Ibaraki that runs in time O(mn + n² 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	United States
City	New Orleans
Period	11/01/2004 → 13/01/2004

Access to Document

Link to publication in Scopus

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

@inproceedings{dca2ee756030497bb9c3feef3d4d28f0,

title = "A deterministic near-linear time algorithm for finding minimum cuts in planar graphs",

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.",

author = "Parinya Chalermsook and Jittat Fakcharoenphol and Danupon Nanongkai",

year = "2004",

language = "English",

volume = "15",

pages = "821--822",

booktitle = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. / Chalermsook, Parinya; Fakcharoenphol, Jittat; Nanongkai, Danupon.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 15 2004. p. 821-822.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - Chalermsook, Parinya

AU - Fakcharoenphol, Jittat

AU - Nanongkai, Danupon

N1 - Conference code: 15

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1842434569&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:1842434569

VL - 15

SP - 821

EP - 822

BT - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -