An efficient algorithm to enumerate sets with fallbacks in a kidney paired donation program. (March 2019)

• Record Type: Journal Article
• Authors: Wang, Wen; Bray, Mathieu; Song, Peter X.K.; Kalbfleisch, John D.
• Is Part Of: Operations research for health care. Volume 20(2019)
• Page Start: 45
• Page End: 55
• Publication Date: 2019-03
• Subjects: Kidney paired donation -- Non-directed donor -- Locally relevant subgraph -- Fallback options -- Breadth-first search; Medical care -- Mathematical models -- Periodicals; Medical policy -- Mathematical models -- Periodicals; Health services administration -- Mathematical models -- Periodicals; Operations research -- Periodicals; Operations Research -- Periodicals; Health Services Research -- Periodicals; Health Policy -- Periodicals; Delivery of Health Care -- Periodicals; 362.106805
• DOI: 10.1016/j.orhc.2018.10.002
• Languages: English
• ISSNs: 2211-6923

Abstract

Abstract: Kidney paired donation is a partial solution to overcoming biological incompatibility preventing kidney transplants. A kidney paired donation (KPD) program consists of altruistic or non-directed donors (NDDs) and pairs, each of which comprises a candidate in need of a kidney transplant and her/his willing but incompatible donor. Potential transplants from NDDs or donors in pairs to compatible candidates in other pairs are determined by computer assessment, though various situations involving either the donor, candidate, or proposed transplant may lead to a potential transplant failing to proceed. A KPD program can be viewed as a directed graph with NDDs and pairs as vertices and potential transplants as edges, where failure probabilities are associated with each vertex and edge. Transplants are carried out in the form of directed cycles among pairs and directed paths initiated by NDDs, which we refer to respectively as cycles and chains. Previous research shows that selecting disjoint subgraphs with a view to creating fallback options when failures occur generates more realized transplants than optimal selection of disjoint chains and cycles. In this paper, we define such subgraphs, which are called locally relevant (LR) subgraphs, and present an efficient algorithm to enumerate all LR subgraphs. Its computational efficiency is significantly better than the previous, more restrictive, algorithms.