Stability Checking

Here's an obvious algorithm for checking if a given marriage is stable.


\begin{algorithm} {Check-Marriage}{R,M} \begin{FOR} {\EACH b \in \{1,n\}} \beg... ...RETURN (b,g) \end{IF} \end{FOR} \end{FOR} \\ \RETURN {\tt True}\end{algorithm}

Here, RB[b] is the ROL for boy b, RG[g] is the ROL for girl g, MB[b] is the mate of boy b in matching M, and MG[g] is the mate of girl g in matching M.

MG[MB[b]] =?.

next up previous
Next: Rank Computation Up: THE STABLE MARRIAGE PROBLEM Previous: Stability