Edmonds-Karp: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 20: Line 20:


'''Break condition:''' There is no flow-augumenting path.
'''Break condition:''' There is no flow-augumenting path.
== Complexity ==
'''Statement:'''
Even if the upper bounds are not integral, the asymptotic complexity is in <math>\mathcal{O}(nm^2)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.
'''Proof:'''

Revision as of 19:49, 12 October 2014

General Information

Algorithmic problem: Max-Flow Problems

Algorithm : This is a minor variation of Ford-Fulkerson: Among all flow-augmenting [math]\displaystyle{ (s,t) }[/math]-paths, always choose one with smallest number of arcs.

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

  1. The flow [math]\displaystyle{ f }[/math] is a fleasible flow.
  2. If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.

Notation: For an [math]\displaystyle{ (s,t) }[/math]-flow, let [math]\displaystyle{ A_f }[/math] denote the set of all arcs that belong to at least one flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path with smallest number of arcs.

Variant:

  1. The smallest number of arcs on a flow-aumenting [math]\displaystyle{ (s,t) }[/math]-path increases (non-strictly) monotonously.
  2. Whenever that number does not decrease in an iteration, the size of [math]\displaystyle{ A_f }[/math] decreases.

Break condition: There is no flow-augumenting path.

Complexity

Statement: Even if the upper bounds are not integral, the asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(nm^2) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math].

Proof: