论文标题
稳定匹配对的图
The Graphs of Stably Matchable Pairs
论文作者
论文摘要
我们通过在存在稳定匹配的匹配时连接具有边缘的元素对，从稳定匹配问题的实例中研究图形。我们的结果包括识别这些图的NP完整性，即在给定图的边缘数量中单独指数的精确识别算法，以及该算法的算法，该算法的时间是在图形的顶点中线性的，但在其雕刻宽度的多项式中指数为指数。我们还提供了属于某些类图的稳定匹配对的图表的特征，以及在这些类中具有图形的稳定匹配的晶格。
We study the graphs formed from instances of the stable matching problem by connecting pairs of elements with an edge when there exists a stable matching in which they are matched. Our results include the NP-completeness of recognizing these graphs, an exact recognition algorithm that is singly exponential in the number of edges of the given graph, and an algorithm whose time is linear in the number of vertices of the graph but exponential in a polynomial of its carving width. We also provide characterizations of graphs of stably matchable pairs that belong to certain classes of graphs, and of the lattices of stable matchings that can have graphs in these classes.
