Give each vertex a strict ordering of its neighbours of a vertex, all preferred to being unmatched. A matching in a graph is stable if no unused edge has both endpoints preferring each other to their current partners, with an unmatched endpoint willing to accept any neighbour. The Gale-Shapley algorithm produces a stable matching even when the two parts have unequal sizes and some pairs are unacceptable.
Articles by others on the same topic
There are currently no matching articles.