A Simple Algorithm for Minimum Cuts in Near-Linear Time

08/30/2019
by   Antonio Molina Lovett, et al.
0

We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger's near-linear time minimum cut algorithm (J. ACM, 2000). We give a self-contained version of Karger's algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log^3 n) time with high probability. This performance matches that achieved by Karger, thereby matching the current state of the art.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset