A Note on the Stable Marriage Problem

Časopis: SN Computer Science

Volume, no: 1 , 2

ISSN: 2661-8907

DOI: 10.1007/s42979-020-00124-z

Stranice: 0-0

Link: https://doi.org/https://doi.org/10.1007/s42979-020-00124-z

Since the pioneering work of Gale and Shapley, the stable marriage problem has received wide treatment by researchers due to its elegance and applicability. The original problem has been generalized and well studied from different angles, and many algorithms have been proposed for the solution of many variants of the traditional formulation. This short note tries to shed some more light on the original algorithm by providing a more direct proof of its correctness.
Ključne reči: Stable marriage problem, Matching problem, Combinatorial algorithm, Gale–Shapley algorithm