<p>There is a randomized algorithm for <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.4293" rel="nofollow">computing Gomory-Hu tree in $\tilde{O}(|E||V|)$ time</a> 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.</p>

CC BY-SA 3.0
2015-02-11T20:45:43.930Z
2015-02-11T20:45:43.930Z
Chao Xu
<p>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:</p>

<p>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$.</p>

<p>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.</p>

<p>Can we do any better?</p>

<graph-algorithms><max-flow-min-cut><max-flow>
Maximum flow for all edges in an undirected graph
meowingDuckling
# Maximum flow for all edges in an undirected graph

(Asked by: username_0 on 2015-02-11)

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?

**Tags:** graph-algorithms, max-flow-min-cut, max-flow

---

## 1 answers

### Answer by username_1 on 2015-02-11. Score: 3

There is a randomized algorithm for [computing Gomory-Hu tree in $\tilde{O}(|E||V|)$ time](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.4293) 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.


---

