P63: Enumeration of all minimum cost perfect matchings in an weighted bipartite graph

P63: Enumeration of all minimum cost perfect matchings in an weighted bipartite graph

Input:

An weighted bipartite graph $B = (V, E)$.

Output:

All minimum cost perfect matchings in $B$.

Complexity:

$O(|V|(|V| + |E|))$ time per solution and $O(|V| + |E|)$ space

Comment:

Reference:

[Fukuda1992] (Bibtex)