Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428825 | Information Processing Letters | 2007 | 4 Pages |
Abstract
Recently, a number of interesting algorithmic problems have arisen from the emergence, in a number of countries, of kidney exchange schemes, whereby live donors are matched with recipients according to compatibility and other considerations. One such problem can be modeled by a variant of the well-known stable roommates problem in which blocking cycles, as well as the normal blocking pairs, are significant. We show here that this variant of the stable roommates problem is NP-complete, thus solving an open question posed by Cechlárová and Lacko.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics