Alternating paths algorithm

From Algowiki
Jump to: navigation, search


Algorithmic Problem: Matchings in graphs.

Prerequisites: The graph [math]G[/math] is bipartite.

Type of algorithm: loop

Auxillary data:

Abstract view

Invariant: Before and after each iteration, [math]M[/math] is a matching.

Variant: [math]|M|[/math] increases by [math]1[/math].

Break condition: There is no more augmenting alternating path.

Induction basis

Abstract view: [math]M[/math] is initialized to be some matching, for example, [math]M:=\empty[/math].

Implementation: Obvious.

Proof: Nothing to show.

Induction step

Abstract view: If there is an augmenting alternating path, use it to increase [math]M[/math]; otherwise, terminate the algorithm and return [math]M[/math].

Implementation:

  1. Call the algorithm Find augmenting alternating path.
  2. If this call fails, terminate the algorithm and return [math]M[/math].
  3. Otherwise, let [math]E'[/math] denote the set of all edges on the path delivered by that call.
  4. Let [math]M[/math] be the symmetric difference of [math]M[/math] and [math]???[/math]

Correctness:

Complexity

Statement:

Proof:

Further information