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_1 be the remaining edges in N. Then and |N_1| <= n_1 and hence 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 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(graph G, node_array<int>& OSC, int heur = 0) | |
computes a maximum cardinality matching M in G and
returns it as a list of edges.
The algorithm ([23], [34]) has running
time O(nm*alpha(n,m)).
With heur = 1 the algorithm uses a greedy heuristic
to find an initial matching.
This seems to have little effect on the running time of the algorithm.
An odd-set cover that proves the maximality of M is returned in OSC.
|
||
list<edge> | MAX_CARD_MATCHING(graph G, int heur = 0) | |
as above, but no proof of optimality is returned. | ||
bool | CHECK_MAX_CARD_MATCHING(graph G, list<edge> M, 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. |