2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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