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

DOI10.1016/0097-3165(87)90037-9zbMath0616.06009MaRDI QIDQ1821125

Paul Leather, Robert W. Irving, Dan Gusfield, Michael E. Saks

Publication date: 1987

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(87)90037-9

zbMATH Keywords

weak dominance; partial order; finite distributive lattice; stable marriage problem; meet-irreducibles; preference list

Mathematics Subject Classification ID

06A06: Partial orders, general

05A05: Permutations, words, matrices

06D05: Structure and representation theory of distributive lattices

Related Items

Review of the theory of stable matchings and contract systems, Marriage and Roommate, Complexity of the sex-equal stable marriage problem, A unifying approach to the structures of the stable matching problems, Interior points in the core of two-sided matching markets, Linear programming brings marital bliss, A new fixed point approach for stable networks and stable marriages, Network flow and 2-satisfiability, Representation of lattices via set-colored posets, An efficient algorithm for batch stability testing, Parameterized complexity and local search approaches for the stable marriage problem with ties, Faster algorithms for stable allocation problems, Entering classes in the college admissions model, Complexity study for the robust stable marriage problem, The graphs of stably matchable pairs, Counterexamples of small size for three-sided stable matching with cyclic preferences, A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences, The Price of Matching with Metric Preferences

Cites Work

• Every finite distributive lattice is a set of stable matchings
• The Complexity of Counting Stable Marriages
• College Admissions and the Stability of Marriage
• Unnamed Item
• Unnamed Item
• Unnamed Item