Three indians' algorithm

From Algowiki
Jump to navigation Jump to search

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 inialized to be feasible, for example, the zero flow.

Proof: Obvious.

Induction step

Remarks

  1. The algorithm is name 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.