Stoer-Wagner Algorithm

The Stoer-Wagner algorithm is a recursive algorithm that solves the minimum cut problem in undirected weighted graphs with non-negative weights, proposed by Mechthild Stoer and Frank Wagner in 1995. It works by repeatedly shrinking the graph, merging its most tightly connected vertices in each phase until only two combined vertex sets remain, finding a minimum cut between two chosen vertices at each phase and keeping the lightest such cut found across all phases as the global minimum cut.