01
Ford-Fulkerson and the Max-Flow Problem
Ford and Fulkerson turned network capacity into an augmenting-path algorithm and a duality theorem: keep pushing additional flow until no source-to-sink residual path remains.
↗
Collection
Ford and Fulkerson turned network capacity into an augmenting-path algorithm and a duality theorem: keep pushing additional flow until no source-to-sink residual path remains.
David Karger's contraction algorithm showed that repeatedly choosing random edges and merging their endpoints could reveal a global minimum cut with analyzable probability.