Ahuja-Orlin: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 12: | Line 12: | ||
# If all upper bounds are integral, <math>f</math> is integral as well. | # If all upper bounds are integral, <math>f</math> is integral as well. | ||
# There is a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> with respect to <math>f</math>. | # There is a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> with respect to <math>f</math>. | ||
# Each node < | # Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which is either void or one of the outgoing arcs of <math>v</math>. | ||
# There is a '''current flow-augmenting path''' with respect to <math>f</math>. This path starts wit <math>s</math> and ends at an arbitrary node of <math>G</math>. Each arc on this path is the curren tarc of its tail. | # There is a '''current flow-augmenting path''' with respect to <math>f</math>. This path starts wit <math>s</math> and ends at an arbitrary node of <math>G</math>. Each arc on this path is the curren tarc of its tail. | ||
Revision as of 09:47, 13 October 2014
General Information
Algorithmic problem: Max-Flow Problems
Type of algorithm: loop
Abstract View
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:
- The flow [math]\displaystyle{ f }[/math] is a fleasible flow.
- If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
- There is a valid distance labeling [math]\displaystyle{ d }[/math] with respect to [math]\displaystyle{ f }[/math].
- Each node [math]\displaystyle{ v\in V\setminus\{t\} }[/math] has a current arc, which is either void or one of the outgoing arcs of [math]\displaystyle{ v }[/math].
- There is a current flow-augmenting path with respect to [math]\displaystyle{ f }[/math]. This path starts wit [math]\displaystyle{ s }[/math] and ends at an arbitrary node of [math]\displaystyle{ G }[/math]. Each arc on this path is the curren tarc of its tail.
Variant: If no arc is appended to tha path in the current iteration, the distance label of some node (the endnode of the path , in fact) is increased.
Break condition: [math]\displaystyle{ d(s)\geq n }[/math].
Induction basis
Induction step
Complexity
Remark
This algorithm may be seen as a "lazy" variant on Edmonds-Karp. In fact, the most expensive step there is the computation of a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. This task amounts to computing the true distance from every node to [math]\displaystyle{ t }[/math]. A valid distance labeling may be seen as "lazily evaluated" true distances.