Three indians' algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 27: | Line 27: | ||
== Remarks == | == Remarks == | ||
# The algorithm is | # 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. | # 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. | ||
Revision as of 16:12, 13 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 inialized to be feasible, for example, the zero flow.
Proof: Obvious.
Induction step
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.