Happy Mutant Profile
Paul Dreyer
John Kessel's wonderful short story collection "The Baum Plan" free CC download
April 16, 2008 7:51am
Mathematics of kidney transplant matching
September 4, 2007 5:19pm
Actually, the graph isn't quite bipartite. For one thing, the goal is to find matching donor/recipient pairs, where the donor of one pair can give a kidney to the recipient of the other pair, and vice versa. You don't want, for example, a volunteer to be used but the recipient they're representing not to receive a kidney in return.
There's two ways to model this:
1. Let donors and recipients be vertices, and add an edge between a donor and a recipient if either the donor has volunteered on behalf of a recipient, or if the donor is a good match for the recipient. Then, search for 4-cycles in the graph. Exercise to the reader to show that a 4-cycle must consist of two volunteer donor/recipient pairs where the donors can cross-transplant the recipients (assuming that a volunteer donor cannot help the recipient s/he is paired with).
2. Let a vertex consist of a donor and (one or more) volunteers associated to that donor. Add edges between two vertices if any of the volunteers in one vertex would be a match to the recipient in the other vertex, and vice versa. Then find a maximum matching.
A noble use for graph theory, to be certain.
No friends yet.


the latest
latest episodes
Sure! The gun is for robbing and looting, and the lunchbox is there because robbing and looting is hard work, and sometimes, you get hungry. Also useful for whacking a bank guard over the head.
I made a MobiPocket version of the book if anyone wants it. If someone would be willing to host it, I would appreciate it. My username at gmail if you can help.