P116: Enumeration of all maximal matchings in a graph

P116: Enumeration of all maximal matchings in a graph

Input:

A graph $G = (V, E)$.

Output:

All maximal matchings in $G$.

Complexity:

$O(|V| + |E| + \Delta N)$ total time and $O(|V| + |E|)$ space.

Comment:

$N$ is the number of solutions and $\Delta$ is the maximum degree in $G$.

Reference:

[Uno2001] (Bibtex)