# Maximum flow for all edges in an undirected graph

I was wondering if the following problem has been studied in the past, and what are some of the best ways people can come up with to solve it:

Let $G=(V,E)$ be an undirected graph, which we use as a flow network with edge capacities $c(e)=1$ for all $e \in E$. For all edges $e = \{u,v\} \in E$, we would like to calculate the maximum flow between $u,v$.

Let $t_{mstf}$ be the time it takes to calculate a maximum s-t flow and $t_{mf}$ be the time it takes to calculate a maximum flow. We can solve the problem above naively in $\mathcal{O}(|E| \cdot t_{mstf})$ time. We can also do it by building a Gomory-Hu tree in $\mathcal{O}(|V| \cdot t_{mf})$ time and then an additional $\mathcal{O}(|E||V|)$ steps to get shortest paths along the tree.

Can we do any better?

There is a randomized algorithm for computing Gomory-Hu tree in $\tilde{O}(|E||V|)$ time when all edges have capacity 1. Once you have the Gomory-Hu tree, you can process it so you can answer maximum flow queries between two vertices in constant time.