Alternating paths algorithm: Difference between revisions

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


'''Algorithmic Problem:''' [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Matchings_in_graphs#Cardinality-maximal_matching\ Maximum matching problem]
'''Algorithmic Problem:''' [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Matchings_in_graphs#Cardinality-maximal_matching\ Maximum matching problem]
'''Prerequisites:''' The graph <math>G</math> is [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Bipartite_graph\ bipartite].
'''Prerequisites:''' The graph <math>G</math> is [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Bipartite_graph\ bipartite].



Revision as of 13:21, 27 January 2015


Algorithmic Problem: Maximum matching problem

Prerequisites: The graph [math]\displaystyle{ G }[/math] is bipartite.

Type of algorithm: loop

Auxillary data:

Abstract view

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

Variant: [math]\displaystyle{ |M| }[/math] increases by [math]\displaystyle{ 1 }[/math].

Break condition: There is no more augmenting alternating path.

Induction basis

Abstract view: [math]\displaystyle{ M }[/math] is initialized to be some matching, for example, [math]\displaystyle{ 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]\displaystyle{ M }[/math]; otherwise, terminate the algorithm and return [math]\displaystyle{ M }[/math].

Implementation:

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

Correctness:

Complexity

Statement:

Proof:

Further information