Mathematics of kidney transplant matching

Right now, there are more than 70,000 people on the waiting list for a kidney transplant in the US alone. Sometimes, a family member will offer to donate a kidney to a relative. That's a really amazing thing to do. The problem is that one-third of the time, the match isn't right. But what if the donor, say, from one family, is a good match for the recipient in another family, and vice versa? According to Science News, researchers at the United States Naval Academy and Johns Hopkins University hope to address this with a mathematical method to "match up the maximum number of donors with recipients while simultaneously guaranteeing high compatibility in each case." The technique is based on graph theory, a way to model the relationship between pairs of objects. From Science News:
 Articles 20070901 F8797 2553 (US Naval Academy mathematician Sommer) Gentry expects that if there were a national registry in place for kidney matching, and if it used her team's method, then each month, about half the pairs in the registry would find a compatible match. Each year, 1,000–2,000 patients would get kidneys who currently would not.

By contrast, as of 2005, only 51 patients had ever received kidneys through a swap in which two incompatible pairs exchange donors to create compatible pairs. Gentry calculates that developing a national registry could save $750 million per year, because dialysis, the only alternative to transplantation, is very expensive.