from some quick search it looks like the online version is an area of active research. you dont mention the application area which might help to narrow down the literature search. one option is to look for an application area where theres the most or latest innovation. hence there is some application of incremental max flow in vision systems & some algorithms for it there; try <a href="http://research.microsoft.com/pubs/150437/ibfs-proc.pdf">Maximum Flows by Incremental Breadth-First Search</a> at microsoft research labs. paraphrasing the intro to this paper, apparently for vision instances the Boykov and Kolmogorov algorithm does well & there are no known exponential time counterexamples although outside of the vision applications it might perform poorly. so it might be worth trying the B&K algorithm on your data & seeing how it performs & also the microsoft algorithm.