Computing at Glasgow University
Paper ID: 8372

The cycle roommates problem: a hard case of kidney exchange

Publication Type: Journal
Appeared in: Information Processing Letters vol. 103
Page Numbers : 1-4
Publisher: Elsevier Science
Year: 2007
ISBN/ISSN: 0020-0190

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 Cechlarova and Lacko.

Keywords: Algorithms, Combinatorial problems, Computational complexity, Matching, Stability

Bibtex entry Endnote XML