In:
Algorithms, MDPI AG, Vol. 12, No. 2 ( 2019-02-25), p. 50-
Abstract:
In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 ≤ L ≤ 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L ≥ 3, and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.
Type of Medium:
Online Resource
ISSN:
1999-4893
Language:
English
Publisher:
MDPI AG
Publication Date:
2019
detail.hit.zdb_id:
2455149-1
Permalink