Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
复制标题
每个有限分配格都是一个小型稳定婚姻实例的一组稳定匹配
DOI：
10.1016/0097-3165(87)90037-9
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
M. Saks
中科院分区：
文献类型：
--
作者：
D. Gusfield;Robert W. Irving;P. Leather;M. Saks
摘要 Blair（J. Combin. Theory Ser. A 37 (1984), 353–356）表明，对于稳定婚姻问题的某些实例，每个有限分配格都是弱支配关系，但对于 k 元素格，实例大小的唯一界限是 2 k。在这篇文章中，我们描述了一种方法，对于任何 k 个元素的分配格 L，构造一个大小至多为 k 2− k+ 4 的实例。此外，我们注意到，如果格 L 的最小实例的大小为 2n，那么本文中的构造的大小至多为 n 4 4。
Abstract Blair (J. Combin. Theory Ser. A 37 (1984), 353–356) showed that every finite distributive lattice is the weak dominance relation for some instance of the stable marriage problem, but the only bound given on the size of the instance was 2 k for a k element lattice. In this note we describe a method which, for any distributive lattice L of k elements, constructs an instance of size at most k 2− k+ 4. Further, we note that if the smallest instance for lattice L has size 2n, then the construction in this paper has size at most n 4 4.