Dynamic Maxflow via Dynamic Interior Point Methods

Jan van den Brand, Yang P. Liu, Aaron Sidford

In this paper we provide an algorithm for maintaining a $(1-\epsilon )$-approximate maximum flow in a dynamic, capacitated graph undergoing edge additions. Over a sequence of $m$-additions…