No Photo

Happy Mutant Profile

Paul Dreyer

John Kessel's wonderful short story collection "The Baum Plan" free CC download

April 16, 2008 7:51am

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.

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.