So the Gale-Shapley algorithm is just one way to output one stable matching instance. Is there any algorithm that can allow us to output all stable matching solutions ? Thanks
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Have you tried backtracking? For most algorithms that finds one solution to a problem, it can be modified to find all solutions, rather easily, for example, by adding backtracking. $\endgroup$– John L.Apr 9, 2020 at 20:08
-
1$\begingroup$ There can be exponentially many solutions, so any such algorithm could potentially take a very long time, depending on the input instance. (But it might be possible to find all solutions in time polynomial in the number of solutions.) $\endgroup$– D.W. ♦Apr 9, 2020 at 20:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Dan Gusfield gave such an algorithm in his paper Three Fast Algorithms for Four Problems in Stable Marriage. The algorithm uses $O(n^2)$ space, and takes time $O(n^2 + nS)$, where $S$ is the number of stable matchings.