Three indians' algorithm: Difference between revisions
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> | '''Abstract view:''' | ||
Choose the node <math>v_0</math> through which the minimum amount of flow may go, and propagate this amount from <math>v_</math> forward to <math>t</math> and backward to <math>s</math>. | |||
'''Implementation:''' | |||
# For each node <math>v\in V\setminus\{s,t\}</math>, let <math>T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\}</math> (the '''throughput''' of node <math>v</math>). | |||
# Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum potential <math>P(v_0)</math>. | # Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum potential <math>P(v_0)</math>. | ||
# | # Set <math>F(v_0):=T(v_0)</math> and <math>T(v):=0</math> for all nodes <math>v\in V\setminus\{s,t\}</math>. | ||
# Run a modified [[Breadth-first search|BFS]] from <math>v</math>, where for every processed arc <math>(v,w)\in A</math>: | |||
## Let <math>\Delta:=\min\{u(v,w),F(v)\}</math>. | |||
## Increase the flow over <math>(v,w)</math> by <math>\Delta</math>. | |||
## Increase <math>F(w)</math> by <math>\Delta</math>. | |||
## Decrease <math>F(v)</math> by <math>\Delta</math>. | |||
## If <math>F(v)=0</math>, remove <math>v</math> and all of its incident arcs. | |||
# Run the same modification from <math>v_0</math> on the [[Basic graph definitions|transpose]] of the graph. | |||
== Remarks == | == Remarks == | ||
Revision as of 03:04, 20 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
Abstract view: Choose the node [math]\displaystyle{ v_0 }[/math] through which the minimum amount of flow may go, and propagate this amount from [math]\displaystyle{ v_ }[/math] forward to [math]\displaystyle{ t }[/math] and backward to [math]\displaystyle{ s }[/math].
Implementation:
- For each node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math], let [math]\displaystyle{ T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\} }[/math] (the throughput 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].
- Set [math]\displaystyle{ F(v_0):=T(v_0) }[/math] and [math]\displaystyle{ T(v):=0 }[/math] for all nodes [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].
- Run a modified BFS from [math]\displaystyle{ v }[/math], where for every processed arc [math]\displaystyle{ (v,w)\in A }[/math]:
- Let [math]\displaystyle{ \Delta:=\min\{u(v,w),F(v)\} }[/math].
- Increase the flow over [math]\displaystyle{ (v,w) }[/math] by [math]\displaystyle{ \Delta }[/math].
- Increase [math]\displaystyle{ F(w) }[/math] by [math]\displaystyle{ \Delta }[/math].
- Decrease [math]\displaystyle{ F(v) }[/math] by [math]\displaystyle{ \Delta }[/math].
- If [math]\displaystyle{ F(v)=0 }[/math], remove [math]\displaystyle{ v }[/math] and all of its incident arcs.
- Run the same modification from [math]\displaystyle{ v_0 }[/math] on the transpose of the graph.
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.