Matchings in graphs

Definition

Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph. A matching in [math]\displaystyle{ G }[/math] is a set [math]\displaystyle{ M }[/math] of edges such that no two edges in [math]\displaystyle{ M }[/math] are incident.

Cardinality-maximal matching

Input: An undirected graph [math]\displaystyle{ G=(V,E) }[/math].

Output: A matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ |M'|\leq|M| }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].

Known algorithms:

1. Maximum matching by Edmonds

Maximum weighted matching

Input:

1. An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
2. A weight [math]\displaystyle{ w(e) }[/math] for each edge [math]\displaystyle{ e\in E }[/math].

Output: A matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \sum_{e\in M'}w(e)\leq\sum_{e\in M}w(e) }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].