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

DOI10.1016/J.IPL.2006.07.005MaRDI QIDQ845882zbMATH OpenOpenAlexFDO

Authors 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

NP-completecombinatorial problemsstable 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)

Recommendations

• Stable matching problems with exchange restrictions
• The exchange-stable marriage problem
• On the complexity of exchange-stable roommates
• scientific article; zbMATH DE number 2086256
• Complexity of the sex-equal stable marriage problem

Cites work

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• College Admissions and the Stability of Marriage
• The Complexity of Counting Stable Marriages
• The complexity of satisfiability problems

Cited in

(4)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845882)