Maximum Cardinality Matchings in General Graphs ( mc_matching )

A matching in a graph G is a subset M of the edges of G such that no two share an endpoint.

An odd-set cover OSC of G is a labeling of the nodes of G with non-negative integers such that every edge of G (which is not a self-loop) is either incident to a node labeled 1 or connects two nodes labeled with the same i, i > = 2.

Let n_i be the number of nodes labeled i and consider any matching N. For i, i > = 2, let N_i be the edges in N that connect two nodes labeled i. Let N₁ be the remaining edges in N. Then | N_i| < = $\lfloor$n_i/2$\rfloor$ and | N₁| < = n₁ and hence

$\Vert N\Vert <= n_1 + \sum_{i >= 2} \lfloor n_i/2 \rfloor$
for any matching N and any odd-set cover OSC.

It can be shown that for a maximum cardinality matching M there is always an odd-set cover OSC with

$\Vert M\Vert = n_1 + \sum_{i >= 2} \lfloor n_i/2 \rfloor,$
thus proving the optimality of M. In such a cover all n_i with i > = 2 are odd, hence the name.

list<edge>	MAX_CARD_MATCHING_EDMONDS(const graph& G, node_array<int>& OSC, int heur=1)
		computes a maximum cardinality matching M in a general graph G and returns it as a list of edges. The original algorithm was developed by Edmond in [27]. An efficient implementation was presented by Gabow and Edmond in [39]. It has running time O(nm*$\alpha$(n, m)). With heur = 1 the algorithm uses a greedy heuristic to find an initial matching. An odd-set cover that proves the maximality of M is returned in OSC.
list<edge>	MAX_CARD_MATCHING_KECECIOGLU(const graph& G, node_array<int>& OSC, int heur=1)
		a variant of Gabow/Edmond's algorithm using an heuristic proposed by J. Kececioglu and J. Pecquer.
list<edge>	MAX_CARD_MATCHING_GABOW(const graph& G, node_array<int>& OSC)
		a new algorithm by Gabow ([40]) with running time O($\sqrt{{n}}$*m). The implementation was done by Ansaripour,Danaei and Mehlhorn ([2]).
bool	CHECK_MAX_CARD_MATCHING(const graph& G, const list<edge>& M, const node_array<int>& OSC)
		checks whether M is a maximum cardinality matching in G and OSC is a proof of optimality. Aborts if this is not the case.
list<edge>	MAX_CARD_MATCHING(const graph& G, node_array<int>& OSC, int heur = 1)
		computes a maximum cardinality matching in a general G and an odd-set cover OSC by calling MAX_CARD_MATCHING_GABOW.
list<edge>	MAX_CARD_MATCHING(const graph& G, int heur = 0)
		as above, but no proof of optimality is returned.