Random sampling in residual graphs

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.

Authors

• David R. Karger
• Matthew S. Levine

Keywords

No keywords are indexed for this paper.