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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.