Question

In all algorithms, always prove why they work. ALWAYS, analyze the complexity of your algorithms. In all algorithms, always try to get the fastest possible.

A matching M = {ei} is maximal if there is no other matching M' so that M ⊆ M' and M /= M' .

Give an algorithm that finds a maximal matching M in polynomial time. The algorithm should be in pseudocode/plain English. Provide the complexity of the algorithm as well.

Answer 1

Maximal matching for a given graph can be found by the simple greedy algorithn below:

Maximal Matching(G, V, E)

1. M = φ

2.While(no more edges can be added)

2.1 Select an edge,e,which does not have any vertex in common with edges in M

2.2 M = M ∪ e

3. return M

Algorithm 2: Algorithm Maximum Matching

Input : A graph G = (V, E).

Output: A matching M of G.

M = {e} for some e ∈ E(G);

while there is an M-augmenting path in G do

Find an M-augmenting path P of G;

M = (M \ E(P)) ∪ (E(P) \ M);

Output(M);