| Random Sampling in Residual Graphs (2008) | |||||||||||||
Abstract | |||||||||||||
| 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. | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||