Three indians' algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 24: | Line 24: | ||
# 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>). | # 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 | # Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum potential <math>P(v_0)</math>. | ||
# | |||
== Remarks == | == Remarks == | ||
Revision as of 21:21, 19 October 2014
General information
Algorithmic problem: Blocking flow.
Type of algorithm: loop.
Abstract view
Invariant: The current flow is feasible.
Variant: The number of nodes strictly decreases.
Induction basis
Abstract view: The flow is initialized to be feasible, for example, the zero flow.
Proof: Obvious.
Induction step
- 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 a node with minimum potential [math]\displaystyle{ P(v_0) }[/math].
Remarks
- 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.