Three indians' algorithm: Difference between revisions

Revision as of 21:16, 19 October 2014

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.

@@ Line 23: / Line 23: @@
 == Induction step ==
+# For each node <math>v\in V\setminus\{s,t\}</math>, let <math>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>v</math>).
+# Let <math>v_0\in V\setminus\{s,t\}</math> be the
 == Remarks ==