On the complexity of exchange-stable roommates

DOI10.1016/S0166-218X(01)00230-XzbMath0996.91011MaRDI QIDQ5957362

Katarína Cechlárova

Publication date: 3 July 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenessexchange stabilitystable roommates problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Individual preferences (91B08)

Related Items (8)

Transfers and exchange-stability in two-sided matching problems ⋮ On (coalitional) exchange-stable matching ⋮ Pareto optimality in coalition formation ⋮ A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem ⋮ Exchange-stability in roommate problems ⋮ Stable matching problems with exchange restrictions ⋮ On the convergence of swap dynamics to Pareto-optimal matchings ⋮ The exchange-stable marriage problem

Cites Work

• Stable marriage and indifference
• Hard variants of stable marriage.
• Three-Dimensional Stabl Matching Problems
• NP-complete stable matching problems
• An efficient algorithm for the “stable roommates” problem
• College Admissions and the Stability of Marriage
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of exchange-stable roommates