Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao (Yu Gao)


We give an algorithm for computing exact maximum flows on graphs with m edges and integer capacities in the range [1, U] in O(m^1.497 polylog(m) log(U)) time. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the O(m^1.5 polylog(m) log(U)) time bound from [Goldberg-Rao JACM '98].

Our algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [M?dry JACM '16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.

Joint work with Yang P. Liu and Richard Peng. https://arxiv.org/abs/2101.07233


2021-04-06  15:00-16:00   


Yu Gao, Georgia Institute of Technology


Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics