Three indians' algorithm

From Algowiki
Revision as of 16:12, 13 October 2014 by Weihe (talk | contribs) (→‎Remarks)
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 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.