A deterministic near-linear time algorithm for finding minimum cuts in planar graphs (SODA’04)

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(mlog3
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.Au

Authors: Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai

mincut

Download: PDFPSPPT

Journal:

Conference: SODA 2004 (Short paper): 15th Annual ACM-SIAM Symposium on Discrete Algorithms [link]

Abstract:

We present a simple deterministic O(n(\log n)^2)-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)^3) and also a deterministic algorithm for general graphs by Nagamochi and Ibaraki that runs in time O(mn+n^2 \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.

Update history:
[v1]: January 2004

Comments are welcomed!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: