Incremental Approximate Maximum Flow in m^1/2+o(1) update time
share
We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m^1/2+o(1)ϵ^-1/2 amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.
READ FULL TEXT