Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao
.We give an algorithm for computing exact maximum flows on graphs with \(m\) edges and integer capacities in the range \([1, U]\) in \(\widetilde{O}(m^{\frac{3}{2} - \frac{1}{328}} \log U)\) time. We use \(\widetilde{O}(\cdot )\) to suppress logarithmic factors in \(m\) . For sparse graphs with polynomially bounded integer capacities, this is …