The Stable/Marriage (SM) problem is a dichotomy matching problem between a group of n men and women, each of whom has a strictly-ordered preference list ranking all the members of the opposite set. The goal is to find a stable matching between the men and women, i.e., a pairing of each man to a woman in such a way that no man and woman who are not assigned to each other would rather be assigned to each other than accept their current assignment.
In 1962, Gale and Shapley described a polynomial-time algorithm to find a stable matching given an instance of SM. This algorithm is popularly known as the Gale-Shapley (GS) algorithm. Subsequently, Gusfield and Irving extended the GS algorithm, in order to reduce the number of operations. The extended algorithm is known as the EGS algorithm. This web application illustrates the execution of both the GS and EGS algorithm on a given instance of SM.