REVIEW 1 cited by
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
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. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the $\widetilde{O}(m^{1.5} \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\k{a}dry JACM `16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.
Forward citations
Cited by 1 Pith paper
-
Approximate Spanning Tree Counting from Uncorrelated Edge Sets
The paper gives an O~(m^1.5 epsilon^-1) time algorithm for approximate spanning tree counting using recursive deletion of uncorrelated edge sets found via electrical-flow localization.
Discussion (0). Continue with ORCID to comment.