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?
0
$\begingroup$
$\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$
$\endgroup$
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).
