1
$\begingroup$

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

$\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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.