Random sampling in residual graphs
Consider an <i>n</i>-vertex, <i>m</i>-edge, undirected graph with maximum flow value <i>v</i>. We give a new <i>Õ</i>(<i>m+nv</i>)-time maximum flow algorithm based on finding augmenting paths in random samples of the edges of residual graphs. After assigning certain special sampling probabilities to edges in <i>Õ</i>(<i>m</i>) time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph.