{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T15:09:44Z","timestamp":1767971384620,"version":"3.49.0"},"reference-count":29,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p> Centralized matching programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs. At the heart of these programs are algorithms to solve kidney exchange problems, which can be modelled as cycle packing problems in a directed graph, involving cycles of length 2, 3, or even longer. Usually, the goal is to maximize the number of transplants, but sometimes the total benefit is maximized by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight in directed graphs. Here we prove the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles. We also present an approximation algorithm and an exact algorithm for the problem of finding a maximum weight exchange involving cycles of bounded length. The exact algorithm has been used to provide optimal solutions to real kidney exchange problems arising from the National Matching Scheme for Paired Donation run by NHS Blood and Transplant, and we describe practical experience based on this collaboration. <\/jats:p>","DOI":"10.1142\/s1793830909000373","type":"journal-article","created":{"date-parts":[[2010,1,6]],"date-time":"2010-01-06T11:38:51Z","timestamp":1262777931000},"page":"499-517","source":"Crossref","is-referenced-by-count":56,"title":["MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS"],"prefix":"10.1142","volume":"01","author":[{"given":"P\u00c9TER","family":"BIR\u00d3","sequence":"first","affiliation":[{"name":"Department of Computing Science, University of Glasgow, Glasgow, G12 8QQ, UK"}]},{"given":"DAVID F.","family":"MANLOVE","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Glasgow, Glasgow, G12 8QQ, UK"}]},{"given":"ROMEO","family":"RIZZI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica ed Informatica (DIMI), Universit\u00e0 di Udine, Italy"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.3.640"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.09.012"},{"key":"rf8","author":"Bir\u00f3 P.","journal-title":"Algorithmica"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00274-0"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.11.009"},{"key":"rf15","first-page":"125","volume":"69","author":"Edmonds J.","journal-title":"J Res. NBS B"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"rf19","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1979"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.11.003"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1137\/0402008"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1097\/TP.0b013e3181901a3d"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90246-E"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/j.transproceed.2004.12.096"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1111\/j.1600-6143.2005.01024.x"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/S0041-1345(98)01655-8"},{"key":"rf27","series-title":"Annals of Discrete Mathematics","volume-title":"Matching Theory","author":"Lov\u00e1sz L.","year":"1986"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/S0041-1345(03)00169-6"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/j.transproceed.2007.02.081"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.100"},{"key":"rf31","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn K.","year":"1999"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1016\/j.transproceed.2004.12.013"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1016\/S0041-1345(98)01659-5"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1162\/0033553041382157"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.04.004"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.3.828"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1097\/01.tp.0000195775.77081.25"},{"key":"rf44","first-page":"2694","volume":"6","author":"Saidman S. L.","journal-title":"Am. J. Transplant."},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1001\/jama.293.15.1883"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:53:52Z","timestamp":1565193232000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":29,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1142\/S1793830909000373"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000373","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}