Gale–Shapley Stable Matching
David Gale & Lloyd Shapley, 1962
O(n²)The deferred-acceptance algorithm (1962) always finds a stable matching for the marriage problem. Free men propose to their next favorite woman; each woman holds her best offer and rejects the rest. Coral lines show current engagements.