Title of article :
The exchange-stable marriage problem Original Research Article
Author/Authors :
Katarina Cechlarova، نويسنده , , David F. Manlove، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2005
Pages :
14
From page :
109
To page :
122
Abstract :
In this paper we consider instances of stable matching problems, namely the classical stable marriage (SM) and stable roommates (SR) problems and their variants. In such instances we consider a stability criterion that has recently been proposed, that of exchange-stability. In particular, we prove that ESM—the problem of deciding, given an SM instance, whether an exchange-stable matching exists—is NP-complete. This result is in marked contrast with Gale and Shapleyʹs classical linear-time algorithm for finding a stable matching in an instance of SM. We also extend the result for ESM to the SR case. Finally, we study some variants of ESM under weaker forms of exchange-stability, presenting both polynomial-time solvability and NP-completeness results for the corresponding existence questions.
Keywords :
Stable marriage problem , Matching , Coalition-exchange-stable , Man-exchange-stable , Stable roommates problem
Journal title :
Discrete Applied Mathematics
Serial Year :
2005
Journal title :
Discrete Applied Mathematics
Record number :
886155
Link To Document :
بازگشت