graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a priority matching (also called: maximum priority matching) is a matching that maximizes the number of high-priority vertices that participate in the matching. Formally, we are given a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

, and a partition of the vertex-set into some subsets, , called ''priority classes''. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from ; subject to this, it saturates the largest number of vertices from ; subject to this, it saturates the largest number of vertices from ; and so on. Priority matchings were introduced by

Alvin Roth Alvin Eliot Roth (born December 18, 1951) is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the Gund professor of economics and business administration emeritus at Harvard University.

Tayfun Sonmez Tayfun is a Turkish name and may refer to: * Tayfun Bademsoy (born 1958), Turkish-German actor * Tayfun Cora (born 1983), Turkish footballer * Tayfun Korkut (born 1974), Turkish footballer * Tayfun Pektürk (born 1988), German footballer * Tayfu ...

and Utku Unver in the context of kidney exchange. In this problem, the vertices are patient-donor pairs, and each edge represents a mutual medical compatibility. For example, an edge between pair 1 and pair 2 indicates that donor 1 is compatible with patient 2 and donor 2 is compatible with patient 1. The priority classes correspond to medical priority among patients. For example, some patients are in a more severe condition so they must be matched first. Roth, Sonmez and Unver assumed that each priority-class contains a single vertex, i.e., the priority classes induce a

total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexiv ...

among the pairs. Later, Yasunori Okumura extended the work to priority-classes that may contain any number of vertices. He also showed how to find a priority matching efficiently using an algorithm for maximum-cardinality matching, with a

run-time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

of . Jonathan S. Turner presented a variation of the augmenting path method (

Edmonds' algorithm In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an ''optimum branching''). It is the directed analog of the minimum spanning tree probl ...

) that finds a priority matching in time . Later, he found a faster algorithm for

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

s: the algorithm runs in time :

O(k , E,  \sqrt )

References

{{Reflist Matching (graph theory)

See also

References