P64: Enumeration of all perfect matchings in a bipartite graph

P64: Enumeration of all perfect matchings in a bipartite graph

Input:

A bipartite graph $B = (U, V, E)$, where $|U| = |V|$.

Output:

All perfect matchings in $B$.

Complexity:

$O(c(|V| + |E|))$ total time and $O(|V| + |E|)$ space, after $O(n^{2.5})$ preprocessing time.

Comment:

$c$ is the number of solutions.

Reference:

[Fukuda1994] (Bibtex)