Worst-case choice for the stable marriage problem (Q1063004)

We present a worst-case choice for the stable marriage problem which takes the maximum number of stages for \textit{D. Gale} and \textit{L. S. Shapely}'s algorithm [Amer. Math. Monthly 69, 9-15 (1962; Zbl 0109.244)]. We also analyze a coroutine solution recently suggested by \textit{L. Allison} [Inf. Process. Lett. 16, 61-65 (1983; Zbl 0513.68064)] as well as a parallel algorithm for this problem.