Dynamic Maxflow via Dynamic Interior Point Methods

van den Brand, J; Liu, YP; Sidford, A

van den Brand, J (通讯作者),Georgia Inst Technol, Atlanta, GA 30332 USA.

PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023; (): 1215

Abstract

In this paper we provide an algorithm for maintaining a (1 - epsilon)-approximate maximum flow in a dynamic, capacitated graph undergoing edge inserti......

Full Text Link