0
$\begingroup$

I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am assuming it means a path from s to t with maximum total capacities once you sum the capacities across the path. However, I am not sure what the term bottleneck adds to the definition nor was I sure if that was correct. Is that the correct definition?

$\endgroup$
  • $\begingroup$ A maximum bottle neck (s-t) path usually refers to a path from s to t that maximizes the capacity of the edge with the smallest capacity on the path (a quick google search could have told you that as well en.wikipedia.org/wiki/Widest_path_problem) $\endgroup$ – Dennis Kraft Oct 23 '15 at 7:07
  • $\begingroup$ @DennisKraft did google but ignored it cuz of the title Widest path problem seemed weird...guess I should have clicked it... $\endgroup$ – Charlie Parker Oct 23 '15 at 7:09
2
$\begingroup$

While I suspect that the notion of "bottleneck" has been introduced in an earlier lesson, it's all in the document you link.

Page 8:

Edmonds and Karp’s first rule is essentially a greedy algorithm:

Choose the augmenting path with largest bottleneck value.

Page 11:

For any flow network $G$ and any vertices $u$ and $v$, let bottleneck $G(u,v)$ denote the maximum, over all paths $\pi$ in $G$ from $u$ to $v$, of the minimum-capacity edge along $\pi$.

This sentence is a bit hard to parse. Unfolded:

Let $P_G(u,v)$ be the set of all $u$-$v$-paths in $G$, and $E(\pi)$ the set of edges that comprise a path $\pi$ in $G$. Then,

$\qquad\displaystyle G(u,v) = \max_{\pi \in P_G(u,v)} \quad \min_{e \in E(\pi)} c(e)$.

Note that $\min_{e \in E(\pi)} c(e)$ is the bottleneck (capacity) of $\pi$.

So Edmongs-Karp picks the $s$-$t$-path with the largest bottleneck (in the residual network), which means it picks the path it can send the most flow over (while maintaining conservation of flows).

$\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.