Random sampling in residual graphs
David R. Karger, Matthew S. Levine · 2002
ABSTRACT Consider an n-vertex, m-edge, undirected graph with maximumflow value v. We give a new ~O (m + nv)-time maximum flow algo-rithm based on finding augmenting paths in random samples of the edges of residual graphs. After assigning certain special samplingprobabilities to edges in ~O (m) time, our algorithm is very simple:repeatedly find an augmenting path in a random sample of edges from the residual graph.