Three indians' algorithm: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 23: Line 23:
== Induction step ==
== 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 ==
== Remarks ==

Revision as of 21:16, 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

  1. 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]).
  2. Let [math]\displaystyle{ v_0\in V\setminus\{s,t\} }[/math] be the

Remarks

  1. The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari.
  2. 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.