A Simple Algorithm for Minimum Cuts in Near-Linear Time

Nalin Bhardwaj, Antonio Molina Lovett, Bryce Sandlund

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…