A Classification of Instances with Graph Equivalence
摘要
The stable marriage problem (SMP) is a combinatorial problem to find stable matching between n women and n men given a complete preference list of men over women and vice versa. An instance of SMP can be expressed by a bipartite graph with multiple (weighted) edges. By rearranging the graph, we use a diagram that involves several constraints to visualize several symmetries. By the diagram, all the instances of the size three SMP (three women and three men) are classified. The classification may be supported by the fact that the same class has the same stable matchings.