Archive for SODA

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 Comment