STOC Conference 2002 Conference Paper
Random sampling in residual graphs
- David R. Karger
- Matthew S. Levine
Consider an n -vertex, m -edge, undirected graph with maximum flow value v . We give a new Õ ( m+nv )-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 Õ ( m ) time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph.