Three indians' algorithm

General information

Algorithmic problem: Blocking flow.

Type of algorithm: loop.

Invariant: The current flow is feasible.

Variant: The number of nodes strictly decreases.

Abstract view: The flow is initialized to be feasible, for example, the zero flow.

Proof: Obvious.

For each node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math], let [math]\displaystyle{ P(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\} }[/math] (the potential of node [math]\displaystyle{ v }[/math]).
Let [math]\displaystyle{ v_0\in V\setminus\{s,t\} }[/math] be the

The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari.
Of course, the nodes need not really be removed from the graph. However, "removed" nodes must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean lable "is removed" does not suffice for that.