= Stable matching in a bipartite graph
= Stable matching
{synonym}
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.
Back to article page
