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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Classification of Instances with Graph Equivalence

  • Yoshiteru Ishida

摘要

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.