Kidney exchange: Further utilization of donors via listed exchange

There is a set of incompatible patient-donor pairs and these pairs are matched pairwise. A match between two pairs corresponds to a paired kidney donation, where pairs exchange donated kidneys, or a paired listed exchange, where the first donor donates a kidney to the deceased donor wait-list, the first patient receives the kidney of the second donor, and the second patient receives a priority on the wait-list. We characterize the set of exchanges with the maximum number of transplants from the set of pairs. This characterization generalizes the well-known Gallai-Edmonds Decomposition Theorem. (C) 2013 Elsevier B.V. All rights reserved.