What is the definition of "augmenting path capacity"?

141 Views Asked by At

I am reading the text "Combinatorial Optimization: Networks and Matroids" by Eugene Lawler.

Notation/Definitions: \begin{align} s, \quad &\text{source vertex} \\ t, \quad &\text{sink vertex} \\ f_e, \quad &\text{flow on edge }e \\ c_e, \quad &\text{capacity of edge }e \\ \text{forward edge}: \quad &\text{edge directed from }s \text{ toward }t \\ \text{backward edge}: \quad &\text{not a forward edge} \end{align} Lawler defines a flow augmenting path (with respect to a given flow $\{f_e\}$) to be an undirected path $P$ from $s$ to $t$ such that all forward edges in $P$ have flow which is strictly less than their capacity (i.e., $f_e < c_e$) and all backward edges in $P$ have flow which is strictly positive (i.e., $f_e > 0$). He then goes on to say,

"The problem of finding a maximum capacity flow augmenting path is evidently quite similar to the problem of finding a shortest path, or, more precisely, a path in which the minimum arc length is maximum."

My question is: What is the definition of the capacity of a flow augmenting path?

1

There are 1 best solutions below

0
On BEST ANSWER

The capacity of a flow augmenting path is $$\min\left(\min_{\text{forward edges $e$}}(c_e-f_e),\min_{\text{backward edges $e$}}f_e\right).$$ It is the amount of flow that can be added along each edge of the path while still respecting $0 \le f_e \le c_e$.