Hardness results on the man-exchange stable marriage problem with short preference lists

DOI10.1016/J.IPL.2006.07.005zbMath1185.68352OpenAlexW2116278637MaRDI QIDQ845882

Christine T. Cheng, Ichiro Suzuki, Eric J. McDermid

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.07.005

zbMATH Keywords

combinatorial problemsNP-completestable marriageman-exchange stable matching

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

On random exchange-stable matchings ⋮ On (coalitional) exchange-stable matching ⋮ A unified approach to finding good stable matchings in the hospitals/residents setting ⋮ Stable matching problems with exchange restrictions

Cites Work

• The Complexity of Counting Stable Marriages
• The complexity of satisfiability problems
• College Admissions and the Stability of Marriage
• Unnamed Item
• Unnamed Item

This page was built for publication: Hardness results on the man-exchange stable marriage problem with short preference lists