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

DOI10.1016/J.IPL.2006.07.005zbMATH Open1185.68352OpenAlexW2116278637MaRDI QIDQ845882FDOQ845882

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

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

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)

Cites Work

• Title not available (Why is that?)
• The Complexity of Counting Stable Marriages
• Title not available (Why is that?)
• The complexity of satisfiability problems
• College Admissions and the Stability of Marriage

Cited In (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

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)