Fast Augmenting Paths by Random Sampling from Residual Graphs

Consider an n-vertex, m-edge, undirected graph with integral capacities and max-flow value v. We give a new [~ over O](m + nv)-time maximum flow algorithm. After assigning certain special sampling probabilities to edges in [~ over O](m)$ time, our algorithm is very simple: repeatedly find an augment...

Full description

Bibliographic Details
Main Authors: Karger, David R., Levine, Matthew S.
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Society for Industrial and Applied Mathematics 2015
Online Access:http://hdl.handle.net/1721.1/97225
https://orcid.org/0000-0002-0024-5847