Note
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance

https://doi.org/10.1016/0097-3165(87)90037-9Get rights and content
Under a Creative Commons license
open archive

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 2k 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 k2k + 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 n44.

Cited by (0)