P85: Enumeration of the $k$ best perfect matchings of a graph

P85: Enumeration of the $k$ best perfect matchings of a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ best perfect matchings of $G$ in decreasing order.

Complexity:

$O(k|V|^3)$ total time with $O(k|V|^2)$ space.

Comment:

Reference:

[Matsui1994] (Bibtex)