A Simple Graph
In this graph there are five nodes and four edges. Note that nodes may have any number of edges connected to them, including zero.
Graphs for KPD Match
In a graph used for kidney donor matching, each node represents an incompatible donor/recipient pair, and each edge represents a possible match.
Optimized Match is based on a matching algorithm from graph theory, which is a branch of applied mathematics. Graph theory deals with the concept of a graph, which is a collection of nodes and edges connecting the nodes (see the example graph drawn on the right).
For the problem of Kidney Paired Donation, we first construct a graph where each node indicates an incompatible donor/recipient pair, and each edge indicates a possible match between the two nodes that it connects. This graph can be constructed by entering blood type, antibody, and HLA information for each pair (node) into a computer. The computer can then determine which pairs are compatible (which matches are possible) and draw edges between these pairs.
Once the graph is constructed and all possible matches are determined, the Optimized Match is run. It compares every possible combination of matches (every feasible solution) to determine the best solution possible for the criteria provided.